Joey LIU | NANTSOU


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * Key point is how to get max sum of the subarray which take a part of head and a part of tail array.
 */
class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int total = 0, localMax = 0, max = Integer.MIN_VALUE, localMin = 0, min = Integer.MAX_VALUE;
        for (int a : A) {
            localMax = Math.max(localMax + a, a);
            max = Math.max(localMax, max);
            localMin = Math.min(localMin + a, a);
            min = Math.min(localMin, min);
            total += a;
        }
        return max > 0 ? Math.max(max, total - min):max;
    }
}