1262. Greatest Sum Divisible by Three

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.

c++

class Solution {
public:
    int maxSumDivThree(vector<int>& A) {
        int res = accumulate(begin(A), end(A), 0);
        int m = res % 3;
        if(m == 0) return res;
        priority_queue<int> pq[3];
        for(auto& a : A) {
            if(a % 3) {
                pq[a%3].push(a);
                while(pq[a%3].size() >= 3) pq[a%3].pop();
            }
        }

        int mi = res;
        if(m == 1) {
            while(pq[1].size() > 1) pq[1].pop();
            if(!pq[1].empty()) mi = min(mi, pq[1].top());
            if(pq[2].size() == 2) {
                int s = pq[2].top(); pq[2].pop();
                s += pq[2].top();
                mi = min(mi, s);
            }
        } else if(m == 2) {
            while(pq[2].size() > 1) pq[2].pop();
            if(!pq[2].empty()) mi = min(mi, pq[2].top());
            if(pq[1].size() == 2) {
                int s = pq[1].top(); pq[1].pop();
                s += pq[1].top();
                mi = min(mi, s);
            }
        }

        return res - mi;
    }
};