1262. 可被三整除的最大和 （dp）

LeetCode： 1262. 可被三整除的最大和

不是连续的 >> 不能用前缀和方式

递归超时

这题是 dp 题

理解：

当前状态 由 上一个状态 转移过来

d p [ i ] [ 0 ] = m a x ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ ∗ ] + n u m s [ i − 1 ] ) ; dp[i][0] = max(dp[i - 1][0], dp[i - 1][*] + nums[i - 1]); dp[i][0]=max(dp[i−1][0],dp[i−1][∗]+nums[i−1]);

方程解释：

当前的 模 0 状态的最大和，由上一个 模 0 状态的最大和 c o m p a r e compare compare 上一个数字(模1) and 上一个状态(模2) 的相加

上一个数字(模1) and 上一个状态(模2) 的相加 >> 模1 + 模2 == 模 0

AC Code

dp

import static java.lang.Math.*;

class Solution {

    public int maxSumDivThree(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len + 1][3];

        dp[0][0] = 0;
        dp[0][1] = Integer.MIN_VALUE;
        dp[0][2] = Integer.MIN_VALUE;
        for (int i = 1; i <= len; i++) {
            if(nums[i - 1] % 3 == 0){
            	// 模 0 的
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][0] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][1] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][2] + nums[i - 1]);
            } else if(nums[i - 1] % 3 == 1){
				// 模 1 的
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + nums[i - 1]);
            } else if(nums[i - 1] % 3 == 2){
                // 模 2 的
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + nums[i - 1]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] + nums[i - 1]);
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + nums[i - 1]);
            }
        }

        return dp[len][0];
    }
    
}

---

递归超时

import static java.lang.Math.*;

class Solution {

    int mx = 0;
    public int maxSumDivThree(int[] nums) {
        dfs(0, nums, 0, nums.length);
        return mx;
    }

    public void dfs(int target, int[] arr, int start, int len){
        if(target % 3 == 0){
            // 被 3 整除
            mx = max(mx, target);
        }
        for (int i = start; i < len; i++) {
            dfs(target + arr[i], arr, i + 1, len);
        }
    }

}

---

LeetCode题解； 动态规划与状态转移