【LeetCode1262】 可被三整除的最大和（动态规划）

【LeetCode1262】 可被三整除的最大和（动态规划）

一、题目

提示：

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 转移方程

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& nums) { int n = nums.size(); vector> dp(n + 1, vector(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]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。