BiliBili

## 原题

### English

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

## Code

class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
vector<int> dp(3, 0), dp2(3, 0);
for (auto& n : nums) {
dp2 = dp;
for (auto& s : dp2) {
dp[(s + n) % 3] = max(s + n, dp[(s + n) % 3]);
}
}
return dp[0];
}
};

## 复杂度分析

本文为原创文章，欢迎分享，勿全文转载，如果内容你实在喜欢，可以加入收藏夹，说不定哪天故事又继续更新了呢。