1262 Greatest Sum Divisible by Three 可被三整除的最大和

Description:

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

Example:

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

题目描述：

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例：

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。

示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。

示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

思路：

动态规划
设 dp[i][j] 表示 nums[:i] 除以 3 余数为 j 的最大的和
初始化 dp[0][0] = 0, dp[0][1] = dp[0][2] = -1
对每个数都可以选或者不选, 对应有 dp[i][j] = max(dp[i - 1][j], dp[i - 1][(j - nums[i]) % 3] + nums[i])
为了避免 (j - nums[i]) 可能存在负数, 可以改写为
dp[i][(j + nums[i]) % 3] = max(dp[i - 1][(j + nums[i]) % 3], dp[i - 1][j] + num)
注意到 dp[i] 只与 dp[i - 1] 有关, 可以用滚动数组压缩空间复杂度到 O(1)
还原时间复杂度为 O(1), 空间复杂度为 O(1), 查找时间复杂度 O(n)

代码:

C++:

class Solution 
{
public:
    int maxSumDivThree(vector<int>& nums)
    {
        vector<int> dp(3);
        dp[1] = dp[2] = INT_MIN;
        for (const auto& num : nums)
        {
            vector<int> dp2(3);
            for (int i = 0; i < 3; i++) dp2[(i + num) % 3] = max(dp[(i + num) % 3], dp[i] + num);
            dp = dp2;
        }
        return dp.front();
    }
};

Java:

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        dp[1] = dp[2] = Integer.MIN_VALUE;
        for (int num : nums) {
            int[] dp2 = new int[3];
            for (int i = 0; i < 3; i++) dp2[(i + num) % 3] = Math.max(dp[(i + num) % 3], dp[i] + num);
            dp = dp2;
        }
        return dp[0];
    }
}

Python:

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0, -float('inf'), -float('inf')]
        for num in nums:
            dp2 = [0] * 3
            for i in range(3):
                dp2[(i + num) % 3] = max(dp[(i + num) % 3], dp[i] + num)
            dp = dp2
        return dp[0]