LeetCode(1262):3つで割り切れる最大およびGreatest Sum Divisible by Three(Java)

2019.11.24 LeetCodeゼロブラシ個人ノートから整理(継続更新)
github:https://github.com/ChopinXBP/LeetCode-Babel
初めての週の試合で、最後にこの01リュックの問題を完全に作らなかったが、その鍵は初期値の設定にある.
dp配列が確立され、dp[i][j]はi番目のビット数(num[i−1])モード3の残数jの最大累積和を表す.
i=0の場合の初期値は{0,−INT,−INT}であり、1番目の数字numが3の倍数であればdp={num,−INT,−INT};そうでなければdp={0,num,−INT}/{0,−INT,num}となる.
i番目のビット数(num[i−1])を使用して、前回の合計となる新しいモード値newmod=(oldmod+num[i−1])%3を計算します.最新の累積と01リュックの構想を通じて動的移動方程式を確立することができる.

dp[i][newmod] = Math.max(dp[i-1][newmod], dp[i-1][oldmod] + nums[i-1]);

トランスポートゲート:3つで割り切れる最大和
Given an array nums of integers, we need to find the maximum possible sum of elements of the array such that it is divisible by three.
整数配列numsをあげます.3で割り切れる要素の最大和を見つけて返してください.

   1：
  ：nums = [3,6,5,1,8]
  ：18
  ：     3, 6, 1   8，      18（   3       ）。

   2：
  ：nums = [4]
  ：0
  ：4     3   ，        ，   0。

   3：
  ：nums = [1,2,3,4,4]
  ：12
  ：     1, 3, 4    4，      12（   3       ）。

  ：
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4

import java.util.Arrays;

/**
 *
 * 5265.          
 *          nums，                  。
 *
 */

public class GreatestSumDivisibleByThree {
    //01  
    public int maxSumDivThree(int[] nums) {
        //dp[i][j]    i   （num[i-1]） 3    j      
        //i=0      {0,-INT,-INT}，  1   num 3   ， dp={num,-INT,-INT}；   ， dp={0,num,-INT}/{0,-INT,num}
        int[][] dp = new int[nums.length + 1][3];
        for(int[] list : dp){
            Arrays.fill(list, Integer.MIN_VALUE);
        }
        dp[0][0] = 0;

        for(int i = 1; i <= nums.length; i++){
            //   i   （num[i-1]），             newmod=(oldmod+num[i-1])%3
            //         01            
            //dp[i][newmod] = Math.max(dp[i-1][newmod], dp[i-1][oldmod] + nums[i-1]);
            for(int j = 0; j < 3; j++){
                int mod = (j + nums[i - 1]) % 3;
                dp[i][mod] = Math.max(dp[i - 1][mod], dp[i - 1][j] + nums[i - 1]);
            }
        }
        return dp[nums.length][0];
    }
}

#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう