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 = 
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, dp = dp = -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].

// 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 = {}, N = A.size();
dp = dp = 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];
}
};


## 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;
}
};


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)
else if (num % 3 == 2)
}
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;
}
}
}

• // 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 = {}, N = A.size();
dp = dp = 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];
}
};

• # 1262. Greatest Sum Divisible by Three
# https://leetcode.com/problems/greatest-sum-divisible-by-three/

class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
n = len(nums)
dp = [0, 0, 0]

for num in nums:

for i in dp[:]:
dp[(i+num)%3] = max(dp[(i+num)%3], num + i)

return dp