918. Maximum Sum Circular Subarray

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

/**
 * Kadane's Algorithm.
 *
 * Refer: (Very Good Explanation)
 * https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass
 *
 * So there are two cases.
 *
 * 1.The result subarray is the middle part. In this case maxSoFar should give
 * the answer.
 *
 * 2. The subarray takes a part of head array and a part of tail array. The
 * maximum result equals to totalSum minus minSoFar.
 *
 * So the max subarray circular sum equals to max(maxSoFar, totalSum - minSoFar)
 *
 * Corner case: If all number are negative, return the maximum one, (which
 * equals to maxSoFar)
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = Length of the input array.
 */
class Solution {
    public int maxSubarraySumCircular(int[] A) throws IllegalArgumentException {
        if (A == null || A.length == 0) {
            throw new IllegalArgumentException("Invalid input. Input array is null or empty");
        }
        if (A.length == 1) {
            return A[0];
        }

        int maxEndingHere = A[0];
        int maxSoFar = A[0];

        int minEndingHere = A[0];
        int minSoFar = A[0];

        int sum = A[0];

        for (int i = 1; i < A.length; i++) {
            maxEndingHere = Math.max(maxEndingHere + A[i], A[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);

            minEndingHere = Math.min(minEndingHere + A[i], A[i]);
            minSoFar = Math.min(minSoFar, minEndingHere);

            sum += A[i];
        }

        return maxSoFar <= 0 ? maxSoFar : Math.max(maxSoFar, sum - minSoFar);
    }
}