【LeetCode1262】 可被三整除的最大和（动态规划）

【LeetCode1262】 可被三整除的最大和（动态规划） 一、题目

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

二、思路

要从给出的数组中，找到一小坨数满足和能被3整除。dp[i][*]表示在num[i]中，被3整除后的余数为*的最大数（和）。

2.1 确定状态

对于每种状态，有2种选择：选择当前元素；不选择当前元素：

	dp[i][*] = max{dp[i-1][*],dp[i-1][*] + nums[i]}  (* 取值为 0,1,2)

2.2 转移方程

（1）零状态：
dp[k][0]:能够被3整除余0的最大数（和）。
d p [ i ] [ 0 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] , { d p [ i − 1 ] [ 0 ] + n u m s [ i ]  nums  [ i ] % 3 = = 0 d p [ i − 1 ] [ 1 ] + n u m s [ i ]  nums  [ i ] % 3 = = 2 d p [ i − 1 ] [ 2 ] + n u m s [ i ]  nums  [ i ] % 3 = = 1 ) d p[i][0]=max left(d p[i-1][0],left{begin{array}{ll} d p[i-1][0]+n u m s[i] & text { nums }[mathrm{i}] % 3==0 \ d p[i-1][1]+n u m s[i] & text { nums }[mathrm{i}] % 3==2 \ d p[i-1][2]+n u m s[i] & text { nums }[mathrm{i}] % 3==1 end{array}right)right. dp[i][0]=max⎝⎛​dp[i−1][0],⎩⎨⎧​dp[i−1][0]+nums[i]dp[i−1][1]+nums[i]dp[i−1][2]+nums[i]​ nums [i]%3==0 nums [i]%3==2 nums [i]%3==1​⎠⎞​
（2）一状态：
dp[k][1]:能够被3整除余1的最大数（和）。 d p [ i ] [ 1 ] = max ⁡ ( d p [ i − 1 ] [ 1 ] , { d p [ i − 1 ] [ 0 ] + n u m s [ i ] ， n u m s % 3 = = 1 d p [ i − 1 ] [ 1 ] + n u m s [ i ] ， n u m s [ i ] % 3 = = 0 d p [ i − 1 ] [ 2 ] + n u m s [ i ] ， n u m s [ i ] % 3 = = 2 ) d p[i][1]=max left(d p[i-1][1],left{begin{aligned} d p[i-1][0]+n u m s[i] & text ， { nums } % 3==1 \ d p[i-1][1]+n u m s[i] & text ，{ nums }[i] % 3==0 \ d p[i-1][2]+n u m s[i] & text ，{ nums }[i] % 3==2 end{aligned}right)right. dp[i][1]=max⎝⎜⎛​dp[i−1][1],⎩⎪⎨⎪⎧​dp[i−1][0]+nums[i]dp[i−1][1]+nums[i]dp[i−1][2]+nums[i]​，nums%3==1，nums[i]%3==0，nums[i]%3==2​⎠⎟⎞​
（3）三状态：
dp[k][2]:能够被3整除余2的最大数（和）。 d p [ i ] [ 2 ] = max ⁡ ( d p [ i − 1 ] [ 2 ] , { d p [ i − 1 ] [ 0 ] + n u m s [ i ] nums ⁡ [ i ] % 3 = = 2 d p [ i − 1 ] [ 1 ] + n u m s [ i ]  nums  [ i ] % 3 = = 1 d p [ i − 1 ] [ 2 ] + n u m s [ i ]  nums  [ i ] % 3 = 0 ) d p[i][2]=max left(d p[i-1][2],left{begin{array}{ll} d p[i-1][0]+n u m s[i] & operatorname{nums}[mathrm{i}] % 3==2 \ d p[i-1][1]+n u m s[i] & text { nums }[mathrm{i}] % 3==1 \ d p[i-1][2]+n u m s[i] & text { nums }[mathrm{i}] % 3=0 end{array}right)right. dp[i][2]=max⎝⎛​dp[i−1][2],⎩⎨⎧​dp[i−1][0]+nums[i]dp[i−1][1]+nums[i]dp[i−1][2]+nums[i]​nums[i]%3==2 nums [i]%3==1 nums [i]%3=0​⎠⎞​

2.3 初始条件+边界

因为当前的状态和前一个状态有关，（我们先将遍历的i从1开始遍历），则其中第0个状态的dp[0][0]表示在nums[0]中，能够被3整除余0的最大数，此时还没遍历到数，dp[0][0] = 0，相当于给数组头添加了0。

还有dp[0][1] = INT_MIN; dp[0][2] = INT_MIN;， 如果设置成0是不符合定义的，dp[0][1]表示的是模三余一，dp[0][2]表示的是模三余二。

这里dp[i][1]和dp[i][2]的初始值可以理解为无穷小，因为dp[i][1]和dp[i][2]的第一个有意义的初始值可以理解为dp[i-1][0]加上数组当前值nums[i]构成的，又因为每次更新三个状态是通过比较最大值获得的，所以无穷小就被干掉了。

举个例子，假设有一个数组中第一个%3余1的数是4，那么在4出现之前，dp[i][1]就一直是无穷小，不会影响dp[i][0]的更新。只有4出现了，才会用dp[i-1][0] + 4去更新dp[i][1]，之后dp[i][1]才会参与dp[i][0]的更新。

2.4 计算顺序

根据递推公式，如dp[i][0]是由dp[i - 1][0]决定的，所以i从小到大顺序遍历。

三、代码

class Solution {
public:
    int maxSumDivThree(vector& nums) {
        int n = nums.size();
        vector> dp(n + 1, vector(3, 0));

        dp[0][0] = 0;
        dp[0][1] = INT_MIN;
        dp[0][2] = INT_MIN;

        for(int i = 1;  i <= n; i++){
            if(nums[i - 1] % 3 == 0){
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]);
            }else if(nums[i - 1] % 3 == 1){
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            }else if(nums[i - 1] % 3 == 2){
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }
        return dp[n][0];
    }
};