PigyChan_LeetCode 1262. 可被三整除的最大和

1262. 可被三整除的最大和

给你一个整数数组 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

思路1.0

将余数和商这两个序列以商的值降序排序，通过两种组合在靠前的元素中选取。
但这种拼凑的方法好像没用上动态规划，要是碰到除数是5或者是更大的素数时，拼凑的组合会变得非常多

思路2.0（已看题解）

记录所有情况的最优子结构，并列出所有情况下状态转移方式，有点类似714. 买卖股票的最佳时机含手续费。
debug的时候发现用这个方法为dp[i][1],dp[i][2]赋第一个有效值的时候要设置为INT_MIN,为了在后面max判断的时候不出错**

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


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


        for (int i = 1; i <= len; ++i)
        {
            int mod = nums[i-1] % 3;


            switch (mod)
            {
            case 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]);
                break;
            case 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]);
                break;
            case 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]);
                break;
            }
        }


        return dp[len][0];
    }
};