、

题解

这道题目核心就算是要知道如果x%3=2的话，应该要去拿%3=1的数字，这样子才能满足%3=0

贪心

sum不够%3的时候，就减去余数为1的或者余数为2的 需要注意 两个余数为1会变成余数为2的，所以可能减去2个余数为1

核心代码如下

public int maxSumDivThreeOther(int[] nums) {
​
   int sum = Arrays.stream(nums).sum();
​
   if (sum%3==0){
       return sum;
  }
​
​
//   要么减去1的 要么减去2的
​
   ArrayList a1 = new ArrayList<>();
   ArrayList a2 = new ArrayList<>();
   for (int i = 0; i < nums.length; i++) { ​        if (nums[i]%3==1){            a1.add(nums[i]);       }        if (nums[i]%3==2){            a2.add(nums[i]);       }   }    Collections.sort(a1);    Collections.sort(a2); //   判断减去哪个    int max=0;    if (sum%3==1&&!a1.isEmpty()){        max=Math.max(max,sum-a1.get(0)); ​ ​   }    if (sum%3==1&&a2.size()>=2){
       max=Math.max(max,sum-a2.get(0)-a2.get(1));
  }
​
   if (sum%3==2&&!a2.isEmpty()){
       max=Math.max(max,sum-a2.get(0));
​
  }
   if (sum%3==2&&a1.size()>=2){
       max=Math.max(max,sum-a1.get(0)-a1.get(1));
​
  }
   return max;
}

dp

不需要知道前面几个选了什么

1.dpi 表示0-i 选了若干个，余数总共是j的 最大数值

然后在前面几个0,i-1选择数值为s的，然后(s+x)%3 =j 算出s=(j-x)%3 这样子，不过如果出现负号的话，还是需要先+3的

如下代码

public int maxSumDivThreeOther2(int[] nums) {
   int n=nums.length;
   //1.dp[i][j] 表示0-i 选了若干个，余数总共是j的 最大数值
   int[][] dp = new int[n+1][3];
​
//   2.递推式 是要求从前i-1个 拿数值s ，要求j的位置上 (s+x)%3==j 所以s=(j-x)%3 由于(j-x)%3 可能是符号 -2 -1 这种 所以要+3
​
   dp[0][0]=0;
   //非法数字 0个数字余数是1 为了避免选择这个 就后续可以让0和Integer.MIN_VALUE比较
   dp[0][1]=Integer.MIN_VALUE;
   dp[0][2]=Integer.MIN_VALUE;
   for (int i = 1; i <= n; i++) {
​
​
       for (int j = 0; j < 3; j++) {
           int pre=(j-nums[i-1])%3;
           if ((j-nums[i-1]) %3<0){
               pre+=3;
          }
           dp[i][j]=Math.max(dp[i-1][j],dp[i-1][pre ]+nums[i-1]);
​
      }
​
​
  }
​
   return dp[n][0];
​
​
}