Formatted question description: https://leetcode.ca/all/1262.html

1262. Greatest Sum Divisible by Three (Medium)

Given an array nums of integers, we need to find 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 * 10^4
  • 1 <= nums[i] <= 10^4

Related Topics:
Dynamic Programming

Solution 1. DP

Let dp[i + 1][r] be the maximum possible sum on the subarray A[0..i] where the current sum modulo 3 is equal to r.

Initially dp[0][0] = 0, dp[0][1] = dp[0][2] = -INF meaning they are invalid states.

dp[i + 1][j] = max(
                    dp[i][j],                            // if we skip A[i]
                    A[i] + dp[i][(j + 3 - A[i] % 3) % 3] // if we pick A[i]
                  )

The result is dp[N][0].

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

// Time: O(N)
// Space: O(N)
class Solution {
public:
    int maxSumDivThree(vector<int>& A) {
        int dp[40001][3] = {}, N = A.size();
        dp[0][1] = dp[0][2] = INT_MIN;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < 3; ++j) dp[i + 1][j] = max(dp[i][j], A[i] + dp[i][(j + 3 - A[i] % 3) % 3]);
        }
        return dp[N][0];
    }
};

Solution 2. DP with Space Optimization

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

// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maxSumDivThree(vector<int>& A) {
        array<int, 3> dp = { 0, INT_MIN, INT_MIN }, tmp;
        for (int n : A) {
            tmp = dp;
            for (int j = 0; j < 3; ++j) dp[j] = max(tmp[j], n + tmp[(j + 3 - n % 3) % 3]);
        }
        return dp[0];
    }
};

Java

class Solution {
    public int maxSumDivThree(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        Arrays.sort(nums);
        int sum = 0;
        List<Integer> ones = new ArrayList<Integer>();
        List<Integer> twos = new ArrayList<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            sum += num;
            if (num % 3 == 1)
                ones.add(num);
            else if (num % 3 == 2)
                twos.add(num);
        }
        if (sum % 3 == 0)
            return sum;
        int onesSize = ones.size(), twosSize = twos.size();
        if (sum % 3 == 1) {
            if (onesSize >= 1 && twosSize >= 2) {
                int min = Math.min(ones.get(0), twos.get(0) + twos.get(1));
                int greatestSum = sum - min;
                return greatestSum;
            } else if (onesSize >= 1) {
                int greatestSum = sum - ones.get(0);
                return greatestSum;
            } else if (twosSize >= 2) {
                int greatestSum = sum - twos.get(0) - twos.get(1);
                return greatestSum;
            } else
                return 0;
        } else {
            if (onesSize >= 2 && twosSize >= 1) {
                int min = Math.min(ones.get(0) + ones.get(1), twos.get(0));
                int greatestSum = sum - min;
                return greatestSum;
            } else if (onesSize >= 2) {
                int greatestSum = sum - ones.get(0) - ones.get(1);
                return greatestSum;
            } else if (twosSize >= 1) {
                int greatestSum = sum - twos.get(0);
                return greatestSum;
            } else
                return 0;
        }
    }
}

All Problems

All Solutions