【状态机DP】力扣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 整除的最大和）。

动态规划

class Solution {
public:int maxSumDivThree(vector<int>& nums) {\int n = nums.size();vector<int> dp(3, INT_MIN);dp[0] = 0;for(int i = 0; i < n; i++){vector<int> g = dp;int k = nums[i] % 3;g[k%3] = max(dp[k%3], dp[0] + nums[i]);g[(1+k)%3] = max(dp[(1+k)%3], dp[1] + nums[i]);g[(2+k)%3] = max(dp[(2+k)%3], dp[2] + nums[i]);dp = move(g);}return dp[0];}
};

时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(1)。

首先我们定义：
dp[0]：当前能被3整除的最大和。
dp[1]：当前除以3余1的最大和。
dp[2]：当前除以3余2的最大和。
没有选任何元素时，和为0是合法的解，并且0是可以被3整除的，所以我们在初始化时，令dp[0] = 0。

我们在进行状态转移的时候，要新建立一个数组，vector<int> g = dp;让g对dp进行深拷贝，新建立一个g数组的作用是，我们在计算第i个元素的时候，如果不使用g数组，而把g数组替换成dp，这会造成dp[1] + nums[i]或dp[2] + nums[i]可能受到前面计算的影响，因为我们转移的dp是之前的状态，而如果直接使用dp，那么有的dp会被更新成目前状态，导致后续计算出错。