Maximum Sum Circular Subarray Solutions in C++

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-06

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


/// Iterate every possible start place
/// For every start point, using Kadane's Algorithm
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();
        int res = *max_element(A.begin(), A.end());
        if(res <= 0)
            return res;

        bool hasNegative = false;
        for(int a: A)
            if(a < 0){
                hasNegative = true;
                break;
            }
        if(!hasNegative)
            return accumulate(A.begin(), A.end(), 0);

        unordered_set<int> visited;
        for(int k = 0; k < A.size(); k ++)
            if(A[k] < 0 && A[(k + 1)%n] >= 0 && !visited.count((k + 1)%n)){
                int start = (k + 1) % n;
                int sum = A[start];
                visited.insert(start);
                for(int i = (start + 1) % n; i != start; i = (i + 1) % n){
                    if(sum > 0)
                        sum += A[i];
                    else{
                        start = i;
                        if(visited.count(start))
                            break;
                        visited.insert(start);
                        sum = A[i];
                    }

                    res = max(res, sum);
                }
            }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-06

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


/// The result should be 1-interval or 2-intervals
/// Using lmin and rmin to get 1-interval result
/// Using lmax and rmax to get 2-interval result
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();

        vector<int> lmin(n + 1, 0);
        int sum = 0;
        for(int i = 0; i < n; i ++){
            sum += A[i];
            lmin[i + 1] = min(lmin[i], sum);
        }

        vector<int> rmin(n + 1, 0);
        sum = 0;
        for(int i = n - 1; i >= 0; i --){
            sum += A[i];
            rmin[i] = min(rmin[i + 1], sum);
        }

        vector<int> lmax(n + 1, 0);
        sum = 0;
        for(int i = 0; i < n; i ++){
            sum += A[i];
            lmax[i + 1] = max(lmax[i], sum);
        }

        vector<int> rmax(n + 1, 0);
        sum = 0;
        for(int i = n - 1; i >= 0; i --){
            sum += A[i];
            rmax[i] = max(rmax[i + 1], sum);
        }

        sum = accumulate(A.begin(), A.end(), 0);
        int res = INT_MIN;
        for(int i = 0; i <= n; i ++)
            res = max(res, sum - lmin[i] - rmin[i]);
        for(int i = 0; i <= n; i ++)
            res = max(res, lmax[i] + rmax[i]);

        if(res == 0)
            res = *max_element(A.begin(), A.end());
        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-06

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


/// The result should be 1-interval or 2-intervals
/// Using Kadane's Algorithm to get 1-interval result
/// Using lmax and rmax to get 2-interval result
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();

        int res = INT_MIN;
        int sum = 0;

        // Kadane's Algorithm
//        for(int i = 0; i < n; i ++){
//            sum += A[i];
//            res = max(res, sum);
//            if(sum < 0)
//                sum = 0;
//        }

        // Kadane's Algorithm
        for(int i = 0; i < n; i ++){
            sum = A[i] + max(sum, 0);
            res = max(res, sum);
        }

        vector<int> lmax(n, A[0]);
        sum = A[0];
        for(int i = 1; i < n; i ++){
            sum += A[i];
            lmax[i] = max(lmax[i - 1], sum);
        }

        vector<int> rmax(n, A[n - 1]);
        sum = A[n - 1];
        for(int i = n - 2; i >= 0; i --){
            sum += A[i];
            rmax[i] = max(rmax[i + 1], sum);
        }

        sum = accumulate(A.begin(), A.end(), 0);
        for(int i = 1; i < n; i ++)
            res = max(res, lmax[i - 1] + rmax[i]);

        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-08

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


/// The result should be 1-interval or 2-intervals
/// Using Kadane's Algorithm to get 1-interval result
/// For 2-interval results, we can also use Kadane's Algorithm's max subarray algorithm
/// Just make every elements in the array into minus :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();

        int res = INT_MIN;
        int sum = 0;

        // Kadane's Algorithm
        for(int i = 0; i < n; i ++){
            sum = A[i] + max(sum, 0);
            res = max(res, sum);
        }

        sum = accumulate(A.begin(), A.end(), 0);
        int sum2 = 0;
        for(int i = 0; i < n; i ++){
            sum2 = -A[i] + max(sum2, 0);
            res = max(res, sum + sum2);
        }

        if(res == 0)
            res = *max_element(A.begin(), A.end());
        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-08

#include <iostream>
#include <vector>
#include <numeric>
#include <unordered_set>

using namespace std;


/// The result should be 1-interval or 2-intervals
/// Using Kadane's Algorithm to get 1-interval result
/// We can also use Kadane's Algorithm's min subarray algorithm to get the 2-interval result
/// It's just the same :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();

        int res = INT_MIN;
        int sum = 0;

        // Kadane's Algorithm
        for(int i = 0; i < n; i ++){
            sum = A[i] + max(sum, 0);
            res = max(res, sum);
        }

        sum = accumulate(A.begin(), A.end(), 0);
        int sum2 = 0;
        for(int i = 0; i < n; i ++){
            sum2 = A[i] + min(sum2, 0);
            res = max(res, sum - sum2);
        }

        if(res == 0)
            res = *max_element(A.begin(), A.end());
        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}

/// Source : https://leetcode.com/problems/maximum-sum-circular-subarray/description/
/// Author : liuyubobobo
/// Time   : 2018-10-08

#include <iostream>
#include <vector>
#include <numeric>
#include <deque>

using namespace std;


/// Make an array of A + A
/// The purpose of this problem is to find the largest subarray in A + A,
/// but length less or equal to len(A)
/// Using stack strategy to keep a mono-space
/// Since we need to make the length less or equal to len(A)
/// deque is actually used (to remove element)
///
/// It'snot a quite efficient algorithm compare to main4 or main5
/// But the thinking and implementation is interesting and good to know
/// (Also hard to think)
/// Please complare this implementation to Leetcode 901 and Leetcode 910 :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {

        int n = A.size();

        vector<int> p(2 * n + 1, 0);
        for(int i = 0; i < n; i ++)
            p[i + 1] = p[n + i + 1] = A[i];
        for(int i = 1; i <= 2 * n; i ++)
            p[i] += p[i - 1];

//        for(int e: p)
//            cout << e << " ";
//        cout << endl;

        int res = INT_MIN;

        deque<int> q;
        q.push_back(0);
        for(int i = 1; i <= 2 * n; i ++){
            if(!q.empty() && i - q.front() > n)
                q.pop_front();

            res = max(res, p[i] - p[q.front()]);

            while(!q.empty() && p[i] <= p[q.back()])
                q.pop_back();

            q.push_back(i);
        }
        return res;
    }
};


int main() {

    vector<int> A1 = {1,-2,3,-2};
    cout << Solution().maxSubarraySumCircular(A1) << endl;
    // 3

    vector<int> A2 = {5,-3,5};
    cout << Solution().maxSubarraySumCircular(A2) << endl;
    // 10

    vector<int> A3 = {3,-1,2,-1};
    cout << Solution().maxSubarraySumCircular(A3) << endl;
    // 4

    vector<int> A4 = {3,-2,2,-3};
    cout << Solution().maxSubarraySumCircular(A4) << endl;
    // 3

    vector<int> A5 = {-2,-3,-1};
    cout << Solution().maxSubarraySumCircular(A5) << endl;
    // -1

    vector<int> A6 = {-2,4,-5,4,-5,9,4};
    cout << Solution().maxSubarraySumCircular(A6) << endl;
    // 15

    vector<int> A7 = {-5,4,-6};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    vector<int> A8 = {-5,-2,5,6,-2,-7,0,2,8};
    cout << Solution().maxSubarraySumCircular(A7) << endl;
    // 4

    return 0;
}