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];
}
};