1262. Greatest Sum Divisible by Three

https://leetcode.com/problems/greatest-sum-divisible-by-three/description/

Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

Constraints:

• 1 <= nums.length <= 4 * 10^4

• 1 <= nums[i] <= 10^4

给定数组nums中满足是三倍数的子集和最大能是多少。优化 + 数组中挑选元素=>DP。分为N步，对于元素i，action分别为选和不选nums[i]，选的话nums[i]能和i前最大子集和余数为0，1和2分别组成凑成新的余数为0, 1和2的和。因此维持dp[i][0:2]表示截止到i元素子集和余数分别为0，1和2的最大子集和是多少，它只和i-1有关因此可以用滚动数组节约空间。

/*
 * @lc app=leetcode id=1262 lang=cpp
 *
 * [1262] Greatest Sum Divisible by Three
 */

// @lc code=start
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp = {0, INT_MIN, INT_MIN};
        for (const auto num : nums) {
            auto n_dp = vector<int>(3, 0);
            for (int i = 0; i < 3; ++i) {
                n_dp[(num + i) % 3] = max(dp[(num + i) % 3], dp[i] + num);
            }
            swap(dp, n_dp);
        }
        return dp[0]; 
    }
};
// @lc code=end