Kadane's Algorithm

Maximum Subarray

class Solution {
    public int maxSubArray(int[] nums) {
        int[] largestSubarrayEndAt = new int[nums.length];
        int max = nums[0];
        largestSubarrayEndAt[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            largestSubarrayEndAt[i] = nums[i] +
                    (largestSubarrayEndAt[i - 1] > 0 ? largestSubarrayEndAt[i - 1] : 0);
            max = Math.max(largestSubarrayEndAt[i], max);
        }

        return max;
    }
}

Maximum Sum Circular Subarray

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxSubarrayEndAt = 0;
        int minSubarrayEndAt = 0;
        int max = nums[0];
        int min = nums[0];
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            maxSubarrayEndAt = nums[i] + Math.max(maxSubarrayEndAt, 0);
            minSubarrayEndAt = nums[i] + Math.min(minSubarrayEndAt, 0);
            max = Math.max(maxSubarrayEndAt, max);
            min = Math.min(minSubarrayEndAt, min);
            sum += nums[i];
        }

        if (min == sum)
            return max;
        else
            return Math.max(sum - min, max);
    }
}