leetcode 1262

问题

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

1
2
3
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:

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

Example 3:

1
2
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

分析

$dp[i][j]$ 表示在 $nums[0…i]$ 中选择一系列数之和除3余 $j \;(j \in [0,2])$ ，的这一些列数的最大值和是多少。于是对于每一个 $nums[i]$ 可以分别与 $dp[i-1][0],\;dp[i-1][1],\;dp[i-1][2]$ 相结合并对相应的值进行更新。注意初始化部分。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(3, INT_MIN));
        // 初始化为0不正确的原因，dp[0][1], dp[0][2] 不可以初始化为0
        // 因为0%3 != 1, 0%3 != 2
        dp[0][nums[0]%3] = nums[0];
        for (int i = 1; i < n; ++i) {
            int y = nums[i]%3;
            dp[i][0] = max(dp[i-1][0], dp[i-1][(3-y)%3] + nums[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][(4-y)%3] + nums[i]);
            dp[i][2] = max(dp[i-1][2], dp[i-1][(5-y)%3] + nums[i]);
            if (dp[i][y] < nums[i])
                dp[i][y] = nums[i];
        }
        return max(dp[n-1][0], 0);
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 经过状态压缩
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp = {0,0,0}, dp2;
        for (int a: nums) {
            dp2 = dp;
            for (int i: dp2) {
                dp[(i+a)%3] = max(dp[(i+a)%3], i+a);
            }
        }
        return dp[0];
    }
};