C++刷leetcode（1262. 可被三整除的最大和***）【动态规划】

糖逗

题目描述：

1. 给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入：nums = [3,6,5,1,8]
   
8. 输出：18
   
9. 解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
   
10. 示例 2：
    
11. 
    
12. 输入：nums = [4]
    
13. 输出：0
    
14. 解释：4 不能被 3 整除，所以无法选出数字，返回 0。
    
15. 示例 3：
    
16. 
    
17. 输入：nums = [1,2,3,4,4]
    
18. 输出：12
    
19. 解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
    
20.  
    
21. 
    
22. 提示：
    
23. 
    
24. 1 <= nums.length <= 4 * 10^4
    
25. 1 <= nums[i] <= 10^4
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/greatest-sum-divisible-by-three
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int maxSumDivThree(vector<int>& nums) {
   
4.         //注意初始化！！！！！
   
5.         int len = nums.size();
   
6.         vector<vector<int> >dp(len, vector<int>(3, INT_MIN));
   
7.         //初始化
   
8.         if(nums[0] % 3 == 0){
   
9.             dp[0][0] = nums[0];
   
10.         }else if(nums[0] % 3 == 1){
    
11.             dp[0][1] = nums[0];
    
12.             dp[0][0] = 0;
    
13.         }else{
    
14.             dp[0][2] = nums[0];
    
15.             dp[0][0] = 0;
    
16.         }
    
17.         //当num[0] % 3 == 1时 dp[0][2]并不等于0，但是dp[0][0]可以等于0，因为0%3 = 0，而！=2；
    
18.         for(int i = 1; i < len; i++){
    
19.             int temp = nums[i];
    
20.             if(temp % 3 == 0){
    
21.                 dp[i][0] = max(dp[i-1][0], dp[i-1][0] + temp);
    
22.                 dp[i][1] = max(dp[i-1][1], dp[i-1][1] + temp);
    
23.                 dp[i][2] = max(dp[i-1][2], dp[i-1][2] + temp);
    
24.             }else if(temp % 3 == 1){
    
25.                 dp[i][0] = max(dp[i-1][0], dp[i-1][2] + temp);
    
26.                 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + temp);
    
27.                 dp[i][2] = max(dp[i-1][2], dp[i-1][1] + temp);
    
28.             }else{
    
29.                 dp[i][0] = max(dp[i-1][0], dp[i-1][1] + temp);
    
30.                 dp[i][1] = max(dp[i-1][1], dp[i-1][2] + temp);
    
31.                 dp[i][2] = max(dp[i-1][2], dp[i-1][0] + temp);
    
32.             }
    
33.         }
    
34.         return dp[len-1][0] == INT_MIN ? 0 : dp[len-1][0];
    
35.     }
    
36. };

复制代码

糖逗

注意初始化！！！！