一、题目

提示：
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)

  

 

  
1
 

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\{

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<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(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];
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/122740419