README_EN.md

1262. Greatest Sum Divisible by Three

中文文档

Description

Given an integer array nums, return the maximum possible sum of elements of the array such that it is divisible by three.

 

Example 1:

Input: nums = [3,6,5,1,8]
Output: 18
Explanation: Pick numbers 3, 6, 1 and 8 their sum is 18 (maximum sum divisible by 3).

Example 2:

Input: nums = [4]
Output: 0
Explanation: Since 4 is not divisible by 3, do not pick any number.

Example 3:

Input: nums = [1,2,3,4,4]
Output: 12
Explanation: Pick numbers 1, 3, 4 and 4 their sum is 12 (maximum sum divisible by 3).

 

Constraints:

• 1 <= nums.length <= 4 * 104
• 1 <= nums[i] <= 104

Solutions

Python3

class Solution:
    def maxSumDivThree(self, nums: List[int]) -> int:
        dp = [0] * 3
        for v in nums:
            a, b, c = dp[0] + v, dp[1] + v, dp[2] + v
            dp[a % 3] = max(dp[a % 3], a)
            dp[b % 3] = max(dp[b % 3], b)
            dp[c % 3] = max(dp[c % 3], c)
        return dp[0]

Java

class Solution {
    public int maxSumDivThree(int[] nums) {
        int[] dp = new int[3];
        for (int v : nums) {
            int a = dp[0] + v, b = dp[1] + v, c = dp[2] + v;
            dp[a % 3] = Math.max(dp[a % 3], a);
            dp[b % 3] = Math.max(dp[b % 3], b);
            dp[c % 3] = Math.max(dp[c % 3], c);
        }
        return dp[0];
    }
}

...