Leetcode 954 Solution

This article provides solution to leetcode question 954 (maximum-sum-circular-subarray)
Categories:
Tags:
Access this page by simply typing in "lcs 954" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/maximum-sum-circular-subarray

Solution

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int opt1 = 0;
        int best1 = INT_MIN;
        int opt2 = 0;
        int best2 = INT_MAX;
        int sum = 0;



        for (int i = 0; i < A.size(); i++)
        {
            int val = A[i];



            opt1 = opt1 < 0 ? val : opt1 + val;
            if (opt1 > best1)
                best1 = opt1;



            opt2 = opt2 > 0 ? val : opt2 + val;
            if (opt2 < best2)
                best2 = opt2;



            sum += val;
        }



        if (sum != best2)
            return max(best1, sum - best2);
        else
            return best1;
    }
};