一、题目
提示：
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的最大数（和）。
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]; } };
