最大子数组
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
注意
子数组最少包含一个数
挑战
要求时间复杂度为O(n)
若当前和小于0，那么加到下一个数上必然会使和减小，此时抛弃这个和重新求和。当遇到一个负数时，记录下当前已知的最大和。
总耗时: 2721 ms
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(int[] nums) {
int sum = nums[0];
int max = nums[0];
for(int i = 1 ;i < nums.length ;i++) {
if(nums[i] < 0) {
if(sum > max) max = sum;
}
if(sum < 0) {
sum = nums[i];
}else {
sum+=nums[i];
}
}
return max>sum?max:sum;
}
}