# 1262. Greatest Sum Divisible by Three

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`

``````class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int res = 0, leftOne = 1e4, leftTwo = 1e4;
for (int num : nums) {
res += num;
if (num % 3 == 1) {
leftTwo = min(leftTwo, leftOne + num);
leftOne = min(leftOne, num);
} else if (num % 3 == 2) {
leftOne = min(leftOne, leftTwo + num);
leftTwo = min(leftTwo, num);
}
}
if (res % 3 == 0) return res;
if (res % 3 == 1) return res - leftOne;
return res - leftTwo;
}
};
``````

``````class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(3));
dp[0] = {0, INT_MIN, INT_MIN};
for (int i = 1; i <= n; ++i) {
int idx = i - 1;
dp[i][0] = max(dp[i - 1][0], dp[i - 1][nums[idx] % 3] + nums[idx]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][(nums[idx] + 1) % 3] + nums[idx]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][(nums[idx] + 2) % 3] + nums[idx]);
}
return dp[n][0];
}
};
``````

``````class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
vector<int> dp(3);
for (int num : nums) {
vector<int> t = dp;
for (int i : t) {
dp[(i + num) % 3] = max(dp[(i + num) % 3], i + num);
}
}
return dp[0];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1262

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

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431077/JavaC%2B%2BPython-One-Pass-O(1)-space

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431108/Java-O(N)-solution-Simple-Math-O(1)-space

https://leetcode.com/problems/greatest-sum-divisible-by-three/discuss/431785/C%2B%2B-Commented-DP-solution-that-actually-makes-sense.

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation