BiliBili
YouTube
原题
中文
给你一个整数数组 nums
,请你找出并返回能被三整除的元素最大和。
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];
}
};
复杂度分析
时间复杂度:O(n)
欢迎分享,引用。若转载,请联系我,谢谢配合。 本文地址:https://qoogle.top/xiaoxu-explaination-leetcode-1262-greatest-sum-divisible-by-three/
[…] 阅读原文 […]