跳到主要内容

1262.可被三整除的最大和

Given an integer array nums, return 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 * 104
  • 1 <= nums[i] <= 104

思路​

贪心+正向思考​

2e8ff83a6993a2e63eb3005d13963fe

int maxSumDivThree(vector<int>& nums) {
    vector<int> n[3];
    for (int a: nums) {
        n[a % 3].push_back(a);
    }
    //记得排序，不然就会出现加了小的，大的没加
    std::sort(n[1].begin(), n[1].end(), greater<>());
    std::sort(n[2].begin(), n[2].end(), greater<>());
    int lb = n[1].size(), lc = n[2].size(), ans = 0;

    //两次的判断
    for (int cntb = lb - 2; cntb <= lb; cntb++) {
        //注意判断cntb是不是小于0的，因为存在lb小于2的情况
        if (cntb >= 0) {
            for(int cntc = lc - 2; cntc <= lc; cntc++){

                if (cntc >= 0 && ((cntb - cntc) % 3 == 0)) {
                    ans = max(ans, std::accumulate(n[1].begin(), n[1].begin() + cntb, 0) +
                                   std::accumulate(n[2].begin(), n[2].begin() + cntc, 0));

                }
            }
        }
    }
    return ans + std::accumulate(n[0].begin(), n[0].end(), 0);
}

2023/06/20 13:26:22 解答成功: 执行耗时:36 ms,击败了61.17% 的C++用户 内存消耗:26.8 MB,击败了33.90% 的C++用户

但是内存消耗的有点多？

  • 1 <= nums.length <= 4 * 10^4

这个量级还是有点大的，((4 10^4)/3)2快排两次

9次的遍历相加，时间复杂的感觉比dp高，不能暂存已经算好的数据

时间复杂度看上去还好，但是还能优化

还有，这是贪心？

破解版（贪心+逆向​

其实你只要全部相加，将最小的两个%1、%2的减去sum能==0就行

用了一个swap来解决逻辑重复的问题。

int maxSumDivThree(vector<int>& nums) {
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    if (sum % 3 == 0) {
        return sum;
    }
    vector<int> n[3];
    for (int a: nums) {
        n[a % 3].push_back(a);
    }
    //记得排序，不然就会出现加了小的，大的没加
    std::sort(n[1].begin(), n[1].end());
    std::sort(n[2].begin(), n[2].end());
    int lb = n[1].size(), lc = n[2].size();

    if (sum % 3 == 2) {
        swap(n[1], n[2]);
    }
    int ans = n[1].size() ? sum - n[1][0] : 0;
    //还有两个1
    if (n[2].size() > 1) {
        ans = max(ans, sum - n[2][0] - n[2][1]);
    }
    return ans;
}

2023/06/20 15:06:31 解答成功: 执行耗时:32 ms,击败了76.58% 的C++用户 内存消耗:25.7 MB,击败了46.38% 的C++用户

一般

不如dp

dp​

依我看，可能需要个二维数组，3*nums大小的

不想看了，没什么心情捏