LeetCode1262：可被三整除的最大和（动态规划）

1262. 可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

 /**
     *  可被三整除的最大和:动态规划
     * dp[i][0]表示nums[0...i]模三余零的最大和
     * dp[i][1]表示nums[0...i]模三余一的最大和
     * dp[i][2]表示nums[0...i]模三余二的最大和
     * 零状态：当前数字最大和模三余零
     * 一状态：当前数字最大和模三余一
     * 二状态：当前数字最大和模三余二
     *
     * 对于任意一种状态，下一步我们都有两种选择，一是选择当前元素，二是不选择当前元素
     * 	dp[i][*] = max{dp[i-1][*],dp[i-1][*] + nums[i]}  (* 取值为 0,1,2)
     * 以上是常见的动态规划的递推结构
     * @param nums
     * @return
     */
    public int maxSumDivThree(int[] nums) {
        int n = nums.length;
        //状态定义：dp[i][j]：nums[0,...,i]模3余j的最大和
        int[][] dp = new int[n+1][3];
        //状态初始化
        dp[0][0] =0;
        dp[0][1] =Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;

        //状态转移方程
        for(int i=1;i<=n;i++){
            if(nums[i-1]%3 ==0){
                //能整除的还能整除
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][0]+nums[i-1]);
                //余1的还是余1
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][1]+nums[i-1]);
                //余2的还是余2
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][2]+nums[i-1]);
            }else if(nums[i-1]%3 == 1){
                //要能整除，两种请情况：不加该数就能整除，或者：之前的和整除余2+该数
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]+nums[i-1]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+nums[i-1]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+nums[i-1]);
            }else if(nums[i-1]%3 ==2){
                dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + nums[i-1]);
                dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2] + nums[i-1]);
                dp[i][2] = Math.max(dp[i-1][2],dp[i-1][0] + nums[i-1]);
            }

        }
        return dp[n][0];
    }