1262. 可被三整除的最大和 (opens new window)

1.动态规划

分析：根据当前元素除3后的余数，进行分类讨论，并且利用子问题的解。

定义dp[i ][j ]表示考虑从0到i的所有整数，除3余数为j的最大整数和，j取值从0到2。

索引i位置进行状态转移时，根据【选或不选】原则进行讨论，举例来说如果当前nums[i]余数为1，那么更新dp[i][2]时，要么选择当前元素合并得到最大整数和dp[i-1][1]+nums[i]；要么不选择得到最大整数和dp[i-1][2]。最后取两个结果的最大值。

注意更新时，需要考虑初始化的问题。如果选择当前元素num[i ]，但dp[i-1][j]等于0未初始化，那么当前位置元素不能选择。

class Solution {
    int res=0;
    public int maxSumDivThree(int[] nums) {
        int[][] dp=new int[nums.length][3];
        dp[0][nums[0]%3]=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]%3==0){
                dp[i][0]=dp[i-1][0]+nums[i];
                dp[i][1]=dp[i-1][1]==0?dp[i-1][1]:dp[i-1][1]+nums[i];
                dp[i][2]=dp[i-1][2]==0?dp[i-1][2]:dp[i-1][2]+nums[i];

            }
            else if(nums[i]%3==1){
                dp[i][0]=dp[i-1][2]==0?dp[i-1][0]:Math.max(dp[i-1][2]+nums[i],dp[i-1][0]);
                dp[i][1]=Math.max(dp[i-1][0]+nums[i],dp[i-1][1]);
                dp[i][2]=dp[i-1][1]==0?dp[i-1][2]:Math.max(dp[i-1][1]+nums[i],dp[i-1][2]);
            }
            else{
                dp[i][0]=dp[i-1][1]==0?dp[i-1][0]:Math.max(dp[i-1][1]+nums[i],dp[i-1][0]);
                dp[i][1]=dp[i-1][2]==0?dp[i-1][1]:Math.max(dp[i-1][2]+nums[i],dp[i-1][1]);
                dp[i][2]=Math.max(dp[i-1][0]+nums[i],dp[i-1][2]);
            }
        }
        return dp[nums.length-1][0];
    }
}

2.优化

由于每次状态转移时，只用到了前一个状态的值，因此开dp数组时不需要开n维，只需要开一个大小为int[3]的数组即可。从而达到O(1)的额外空间。