class Solution {
public int maxSumDivThree(int[] nums) {
int res = 0, leftOne = 20000, leftTwo = 20000;
for(int n:nums){
res+=n;
if(n%3==1){
leftTwo = Math.min(leftTwo,leftOne+n);
leftOne = Math.min(leftOne,n);
}
if(n%3==2) {
leftOne = Math.min(leftOne,leftTwo+n);
leftTwo = Math.min(leftTwo,n);
}
}
if(res%3==0) return res;
if(res%3==1) return res-leftOne;
return res - leftTwo;
}
}
Dp solution for K problem:
class Solution {
public int maxSumDivThree(int[] nums) {
return maxSumDivK(nums,3);
}
public int maxSumDivK(int[] nums, int k){
if(k==0) return -1;
int[] dp = new int[k];
for(int num : nums){
int tmp[] = Arrays.copyOf(dp,k);
for(int i=0;i<k;i++){
dp[(num+tmp[i])%k] = Math.max(dp[(num+tmp[i])%k],num+tmp[i]);
}
}
return dp[0];
}
}
See why 4M developers consider Sentry, “not bad.”
Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)