小旭讲解 LeetCode 1262. Greatest Sum Divisible by Three

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/