给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
子数组最少包含一个数
要求时间复杂度为O(n)
解题思路：这道题应该是非常常见的ACM的入门试题。算法有很多种， 我参考的算法总结如下：
<1>假设前k个数的和sum已经计算出来
<2>对于第k+1个数来说，如果sum<0，则说明前k个绝不可能是最长上升连续子序列，即默认sum=0，从k+1个数重新开始计算
<3>不允许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
int n;
int sum = nums[0];
int Maxsum = nums[0];
n = nums.length;
for(int i=1;i<n;i++){
if(sum <0){
sum = 0;
}
sum+=nums[i];
Maxsum = Math.max(Maxsum,sum);
}
return Maxsum;
}
}
原文：http://www.cnblogs.com/wangnanabuaa/p/5149820.html