最大子序列问题
给定一个数列，其中的数有正有负，求这个数列中的某一个子序列使得它们的和最大。
例如：
-2, 11, -4, 13, -5, 2, -5, -3, 12, -9 这个数列中，子序列和最大为21
-2 ,11, -4, 13, -5, -2 和为20 思路：
traverse整个数组
用sum存储当前位置及其之前的数字之和
因为每次循环都会求得一个sum，用max存储最大的sum
如果某一次求得的sum<0，则另sum=0，意思是抛弃之前所有的元素，从之后的元素重新开始求和。
public class Maxsubarray {
public int maxsum(int[] array){
if(array.length == 0) return 0;
else if(array.length == 1) return array[0];
else{
int sum = 0;
int max = sum;
for(int i = 0; i < array.length; i++){
if(max < sum) max = sum;
sum = sum + array[i];
if(sum < 0)
sum = 0;
}
return max;
}
}
public static void main(String[] args) {
int array[] = {-2 ,11, -4, 13, -5, -2};
Maxsubarray ms = new Maxsubarray();
System.out.println(ms.maxsum(array));
}
}
时间复杂度由n规模的for循环贡献，因此是O(n)
