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

# 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`

给定数组nums中满足是三倍数的子集和最大能是多少。优化 + 数组中挑选元素=>DP。分为N步，对于元素i，action分别为选和不选nums\[i]，选的话nums\[i]能和i前最大子集和余数为0，1和2分别组成凑成新的余数为0, 1和2的和。因此维持dp\[i]\[0:2]表示截止到i元素子集和余数分别为0，1和2的最大子集和是多少，它只和i-1有关因此可以用滚动数组节约空间。

```cpp
/*
 * @lc app=leetcode id=1262 lang=cpp
 *
 * [1262] Greatest Sum Divisible by Three
 */

// @lc code=start
class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp = {0, INT_MIN, INT_MIN};
        for (const auto num : nums) {
            auto n_dp = vector<int>(3, 0);
            for (int i = 0; i < 3; ++i) {
                n_dp[(num + i) % 3] = max(dp[(num + i) % 3], dp[i] + num);
            }
            swap(dp, n_dp);
        }
        return dp[0]; 
    }
};
// @lc code=end


```
