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.)

Example 1:

Input: [1,-2,3,-2]
Output: 3

Approach

Java

public class MaxSumCircularSub {
    public static void main(String[] args) {
        int[] nums = { 1, -2, 3, -2 };
        System.out.println(maxSubarraySumCircular(nums));
    }

    static int maxSubarraySumCircular(int[] A) {
        if (A.length == 0)
            return 0;
        int y = kadane(A);
        int x = 0;
        for (int i = 0; i < A.length; i++) {
            x += A[i];
            A[i] = -A[i];
        }
        x = x + kadane(A);
        if (x == 0 && y < 0)
            return y;
        return Math.max(y, x);
    }

    static int kadane(int[] A) {
        int max_sum = A[0];
        int sum = A[0];
        for (int i = 1; i < A.length; i++) {
            // if sum becomes zero or negative then
            // make it as 0
            if (sum <= 0)
                sum = 0;
            // add current element into sum
            sum += A[i];

            // update the max_sum
            max_sum = Math.max(sum, max_sum);
        }
        // return the max sum
        return max_sum;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int kadane(vector<int> &A)
{
    int max_sum = A[0];
    int sum = A[0];
    for (int i = 1; i < A.size(); i++)
    {
        // if sum becomes zero or negative then
        // make it as 0
        if (sum <= 0)
            sum = 0;
        // add current element into sum
        sum += A[i];

        // update the max_sum
        max_sum = max(sum, max_sum);
    }
    // return the max sum
    return max_sum;
}
int maxSubarraySumCircular(vector<int> &A)
{
    if (A.size() == 0)
        return 0;
    int y = kadane(A);
    int x = 0;
    for (int i = 0; i < A.size(); i++)
    {
        x += A[i];
        A[i] = -A[i];
    }
    x = x + kadane(A);
    if (x == 0 && y < 0)
        return y;
    return max(y, x);
}

int main()
{
    vector<int> nums = {1, -2, 3, -2};
    cout << maxSubarraySumCircular(nums);
    return 0;
}