Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6

maxSubArray.java

public int maxSubArray(int[] nums) {
    if(nums.length == 0) return 0;

    int localMax = nums[0];
    int globalMax = localMax;

    for(int i = 1; i < nums.length; i++) {
        localMax = Math.max(nums[i], localMax + nums[i]);
        globalMax = Math.max(localMax, globalMax);
    }

    return globalMax;
}