1262. Greatest Sum Divisible by Three

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

本题给我们一个数字数组 nums，要求我们算出 nums 中最大的可以被 3 整除的和是多少

解题思路

我们假设数组 nums 所有元素总和为 sum，sum 除以 3 的余数可能为 0，1，2

如果余数为 1，有两种方式可以让 sum 可以被 3 整除：

1. 我们从数组中选出余数为 1 的元素中最小的元素（假设是 num1），sum - num1 可以被 3 整除
2. 我们从数组中选出余数为 2 的元素，然后选取其中最小的两个元素（假设是 num2, num3），sum - (num2 + num3) 可以被 3 整除

我们要做的，就是在 num1 与 num2 + num3 中找出一个最小值，使得剩下的 sum 值最大化

余数为 2 的情况正好与余数为 1 的情况相反

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumDivThree = function (nums) {
    // the max possible of nums[i]
    let remain1 = remain2 = 10 ** 4
    let sum = 0

    // if sum of nums' remainder is 1, there are two posibilities: 
    // 1. We select one smallest element in the array with a remainder of 1
    // 2. We select two smallest elements in the array with a remainder of 2
    // we want to choose the minimum(**remain1**) so the sum can be as big as possible
    // --------
    // if sum of nums' remainder is 2, vice versa 
    // the minumum should be **remain2**
    nums.forEach(num => {
        sum += num
        if (num % 3 === 1) {
            remain2 = Math.min(remain2, remain1 + num)
            remain1 = Math.min(remain1, num)
        } else if (num % 3 === 2) {
            remain1 = Math.min(remain1, remain2 + num)
            remain2 = Math.min(remain2, num)
        }
    })

    switch (sum % 3) {
        case 0:
            return sum
        case 1:
            return sum - remain1
        case 2:
            return sum - remain2
    }
};