1262. 可被三整除的最大和

小貼士：C++的array能用來設定固定大小的陣列，不過裡面的元素可以放容器。

思路

題目要選出一些數字，最大化總和，並且總和是三的倍數。
我們能將思路逆轉過來，數組的總和sum盡量減去小的數字，讓總合是三的倍數。

先統計 nums[i] % 3 = 1, 2 各自都有哪些數字。

• 假如現在sum % 3 = 1，可以減去一個餘數為 1 的數字，或是減去兩個餘數為 2 個數字。
• 假如現在sum % 3 = 2，可以減去一個餘數為 2 的數字，或是減去兩個餘數為 1 的數字。 減去時選擇最小的數字，答案就出來了。

程式碼

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int sum = reduce(nums.begin(), nums.end(), 0);
        if(sum % 3 == 0) {
            return sum;
        }
        array<vector<int>, 3> arr; // 餘 1, 餘 2
        for(int x : nums) {
            arr[x % 3].push_back(x);
        }
        ranges::sort(arr[1]);
        ranges::sort(arr[2]);
        if(sum % 3 == 2) {
            swap(arr[1], arr[2]);
        }
        int res = arr[1].size() ? sum - arr[1][0] : 0;
        if(arr[2].size() > 1) {
            res = max(res, sum - arr[2][0] - arr[2][1]);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$