Description

Submission

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int sum = 0;
        int n = nums.size();

        for(auto i: nums) {
            sum += i;
        }

        if(sum % 3 == 0) return sum;

        priority_queue<int, vector<int>, greater<int>> pq1;
        priority_queue<int, vector<int>, greater<int>> pq2;

        for(auto n : nums) {
            int tmp = n % 3;
            if(tmp == 1) pq1.push(n);
            if(tmp == 2) pq2.push(n);
        }

        vector<int> res;
        int cmp = INT_MAX;
        if(sum % 3 == 1) {
            if(!pq1.empty()) {
                cmp = pq1.top();
            }
            while(!pq2.empty() && res.size() < 2) {
                res.push_back(pq2.top());
                pq2.pop();
            }
        }

        if(sum % 3 == 2) {
            if(!pq2.empty()) {
                cmp = pq2.top();
            }
            while(!pq1.empty() && res.size() < 2) {
                res.push_back(pq1.top());
                pq1.pop();
            }
        }

        if(res.size() != 2) {
            if(cmp != INT_MAX) {
                return sum - cmp;
            } else {
                return 0;
            }
        }

        return max(sum - res[0] - res[1], sum - cmp);
    }
};