Maximum Subarray

Given an array of integers, find a contiguous subarray which has the largest sum.
** Notice
The subarray should contain at least one number.

ExampleGiven the array [−2,2,−3,4,−1,2,1,−5,3]
, the contiguous subarray [4,−1,2,1]
has the largest sum = 6

贪心算法，据说linkedin面试题，首先我们用一个max来存储当前最大的sum值，然后不断更新它。
在遍历数组里面，我们首先把当前数加入sum中求和，然后和max对比取最大值存入max，
最后我们把sum和0对比取大值，如果sum大于0我们继续往里面加来看，如果小于0我们之间清零，也就是说把之前的连续和给否定掉，从新开始求和。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if(nums == null || nums.length == 0) {
            return -1;
        }
        
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i=0; i < nums.length; i++) {
            sum += nums[i];
            max = Math.max(max, sum);
            sum = Math.max(sum, 0);
        }
        return max;
        

    }
}