1262. 可被三整除的最大和
提示
给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。
思路：
方法一：利用一个长度为3的数组，分别保存0到i内余数为0，1，2的最大和，这样对于一个进入的数k，依次更新数组每一个元素，最后dp[0]就是所要求的结果.
方法二：先整体求出所有数的和sum，然后判断宿命对3的余数，如果是0，则直接返回。若是1，则结果可能是sum减去一个余数是1的元素，或者sum减去两个余数是二的元素。若是2，则结果可能是sum减去一个余数是2的元素，或者sum减去两个余数是一的元素。
class Solution {
public:int maxSumDivThree(vector<int>& nums) {// vector<int>dp(3,0);// //和余是0，1，2// for(int i=0;i<nums.size();i++)// {// int ret=nums[i]%3;// vector<int>dp1(dp.begin(),dp.end());// //和余是0，1，2// if(dp[ret]==0)// {// dp1[ret]=nums[i];// }// for(int k=0;k<3;k++)// {// {// if(dp[k]!=0)// {// //非零才能用来更新// dp1[(k+ret)%3]=max(dp[(k+ret)%3],dp[k]+nums[i]);// }// }// }// dp=dp1;// }// return dp[0]; const int cc=0x3f3f3f3f;vector<int>dp(3,cc);vector<int>dp1(3,cc);int sum=0;for(auto e:nums){ sum+=e;int ret=e%3;if(dp[ret]>e){dp1[ret]=dp[ret];dp[ret]=e;}else{dp1[ret]=min(dp1[ret],e);}} if(sum%3==0){return sum;}else if(sum%3==1){if(dp[1]==cc&&dp1[2]==cc){return 0;}else{return max(sum-dp[1],sum-dp[2]-dp1[2]);}}else{if(dp[2]==cc&&dp1[1]==cc){return 0;}else{return max(sum-dp[2],sum-dp[1]-dp1[1]);}}}
};
