918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array. (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once. (Formally, for a subarray C[i], C[i+1], …, C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

• new solution on 2022.02.02

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int curMax = 0, maxSum = INT_MIN, curMin = 0, minSum = INT_MAX, tot = 0;
        for(auto& n : nums) {
            curMax = max(curMax + n, n);
            maxSum = max(maxSum, curMax);
            curMin = min(curMin + n, n);
            minSum = min(minSum, curMin);
            tot += n;
        }

        return tot == minSum ? maxSum : max(maxSum, tot - minSum);
    }
};

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        vector<int> sum(A.size() * 2, 0);
        int res = INT_MIN, sz = A.size();
        pair<int, int> minP{0, 0}, maxP{0, 0};
        priority_queue<pair<int, int>> minPQ;
        minPQ.push({0, 0});
        for(int i = 0; i < sz; i++) {
            sum[i + 1] = sum[i] + A[i];
            minPQ.push({-sum[i + 1], i + 1});
            if(sum[i + 1] >= maxP.first) {
                res = max(res, sum[i + 1] - minP.first);
                maxP.first = sum[i + 1];
                maxP.second = i;
            } else if(sum[i + 1] <= minP.first) {
                res = max(res, sum[i + 1] - minP.first);
                minP = maxP = {sum[i + 1], i};
            }
        }

        for(int i = 0; i < sz - 1; i++) {
            sum[i + sz + 1] = sum[i + sz] + A[i];
            minPQ.push({-sum[i + 1 + sz], i + sz + 1});
            if(sum[i + 1 + sz] >= maxP.first) {
                if(minP.second <= i + 1) {
                    while(!minPQ.empty() && minP.second <= i + 1) {
                        minP = minPQ.top();
                        minPQ.pop();
                    }
                    minP.first *= -1;
                }
                res = max(res, sum[i + 1 + sz] - minP.first);
                maxP.first = sum[i + 1 + sz];
                maxP.second = i + sz;
            } else if(sum[i + 1 + sz] <= minP.first) {
                if(minP.second <= i + 1) {
                    while(!minPQ.empty() && minP.second <= i + 1) {
                        minP = minPQ.top();
                        minPQ.pop();
                    }
                    minP.first *= -1;
                }
                res = max(res, sum[i + 1 + sz] - minP.first);
                minP = maxP = {sum[i + 1 + sz], i + sz};
            }
        }

        return res;
    }
};