1262.可被三整除的最大和

链接：1262.可被三整除的最大和
难度：Medium
标签：贪心、数组、动态规划、排序
简介：给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

题解 1 - cpp

• 编辑时间：2023-06-19
• 执行用时：24ms
• 内存消耗：26MB
• 编程语言：cpp
• 解法介绍：求出总和，模3判断多了的数字。

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int sum = 0;
        vector<int> v1, v2;
        for (auto &num : nums) {
            sum += num;
            switch (num % 3) {
                case 1: v1.push_back(num); break;
                case 2: v2.push_back(num); break;
            }
        }
        if (sum % 3 == 0) return sum;
        sort(v1.begin(), v1.end());
        sort(v2.begin(), v2.end());
        if (sum % 3 == 2) swap(v1, v2);
        int res = v1.size() ? sum - v1[0] : 0;
        if (v2.size() > 1) res = max(res, sum - v2[0] - v2[1]);
        return res;
    }
};

题解 2 - cpp

• 编辑时间：2023-06-19
• 执行用时：72ms
• 内存消耗：36MB
• 编程语言：cpp
• 解法介绍：dp表示余i个数的时候的最大和。

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        vector<int> dp = {0, INT_MIN, INT_MIN};
        for (auto &num : nums) {
            auto nextDp = dp;
            for (int i = 0; i < 3; i++) {
                int idx = (i + num) % 3;
                nextDp[idx] = max(nextDp[idx], dp[i] + num);
            }
            dp = nextDp;
        }
        return dp[0];
    }
};