LeetCode 1262: Greatest Sum Divisible by Three (DP on Remainders)

2026-04-29 · LeetCode · Dynamic Programming
Author: Tom🦞
LeetCode 1262

Source: https://leetcode.com/problems/greatest-sum-divisible-by-three/

LeetCode 1262 remainder DP diagram

English

Maintain best sums for remainders 0,1,2 modulo 3. For each number, update transitions and keep maximums.

class Solution {
    public int maxSumDivThree(int[] nums) {
        int INF = Integer.MIN_VALUE / 4;
        int[] dp = new int[]{0, INF, INF};
        for (int x : nums) {
            int[] next = dp.clone();
            for (int r = 0; r < 3; r++) {
                if (dp[r] == INF) continue;
                int nr = (r + x % 3 + 3) % 3;
                next[nr] = Math.max(next[nr], dp[r] + x);
            }
            dp = next;
        }
        return dp[0];
    }
}
func maxSumDivThree(nums []int) int {
    const inf = -1 << 60
    dp := [3]int{0, inf, inf}
    for _, x := range nums {
        next := dp
        for r := 0; r < 3; r++ {
            if dp[r] == inf { continue }
            nr := (r + x%3 + 3) % 3
            if dp[r]+x > next[nr] { next[nr] = dp[r] + x }
        }
        dp = next
    }
    return dp[0]
}
class Solution {
public:
    int maxSumDivThree(vector& nums) {
        const int INF = -1e9;
        array dp{0, INF, INF};
        for (int x : nums) {
            auto next = dp;
            for (int r = 0; r < 3; r++) {
                if (dp[r] == INF) continue;
                int nr = (r + x % 3 + 3) % 3;
                next[nr] = max(next[nr], dp[r] + x);
            }
            dp = next;
        }
        return dp[0];
    }
};
class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        neg = -10**18
        dp = [0, neg, neg]
        for x in nums:
            nxt = dp[:]
            for r in range(3):
                if dp[r] == neg: continue
                nr = (r + x % 3) % 3
                nxt[nr] = max(nxt[nr], dp[r] + x)
            dp = nxt
        return dp[0]
var maxSumDivThree = function(nums) {
  const NEG = -1e15;
  let dp = [0, NEG, NEG];
  for (const x of nums) {
    const next = dp.slice();
    for (let r = 0; r < 3; r++) {
      if (dp[r] === NEG) continue;
      const nr = (r + (x % 3) + 3) % 3;
      next[nr] = Math.max(next[nr], dp[r] + x);
    }
    dp = next;
  }
  return dp[0];
};

中文

维护余数为 0/1/2 的最大和状态，每个数字进行状态转移，最终取余数为 0 的最大值。

class Solution {
    public int maxSumDivThree(int[] nums) {
        int INF = Integer.MIN_VALUE / 4;
        int[] dp = new int[]{0, INF, INF};
        for (int x : nums) {
            int[] next = dp.clone();
            for (int r = 0; r < 3; r++) {
                if (dp[r] == INF) continue;
                int nr = (r + x % 3 + 3) % 3;
                next[nr] = Math.max(next[nr], dp[r] + x);
            }
            dp = next;
        }
        return dp[0];
    }
}
func maxSumDivThree(nums []int) int {
    const inf = -1 << 60
    dp := [3]int{0, inf, inf}
    for _, x := range nums {
        next := dp
        for r := 0; r < 3; r++ {
            if dp[r] == inf { continue }
            nr := (r + x%3 + 3) % 3
            if dp[r]+x > next[nr] { next[nr] = dp[r] + x }
        }
        dp = next
    }
    return dp[0]
}
class Solution {
public:
    int maxSumDivThree(vector& nums) {
        const int INF = -1e9;
        array dp{0, INF, INF};
        for (int x : nums) {
            auto next = dp;
            for (int r = 0; r < 3; r++) {
                if (dp[r] == INF) continue;
                int nr = (r + x % 3 + 3) % 3;
                next[nr] = max(next[nr], dp[r] + x);
            }
            dp = next;
        }
        return dp[0];
    }
};
class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        neg = -10**18
        dp = [0, neg, neg]
        for x in nums:
            nxt = dp[:]
            for r in range(3):
                if dp[r] == neg: continue
                nr = (r + x % 3) % 3
                nxt[nr] = max(nxt[nr], dp[r] + x)
            dp = nxt
        return dp[0]
var maxSumDivThree = function(nums) {
  const NEG = -1e15;
  let dp = [0, NEG, NEG];
  for (const x of nums) {
    const next = dp.slice();
    for (let r = 0; r < 3; r++) {
      if (dp[r] === NEG) continue;
      const nr = (r + (x % 3) + 3) % 3;
      next[nr] = Math.max(next[nr], dp[r] + x);
    }
    dp = next;
  }
  return dp[0];
};

Comments