算法一：
思想分析：
要求解序列中最大的和，那么需要得到，每个序列的和，并比较值
int[] a = {-1, 0, 1, 2, -3, 8, 6};
[-1]
[-1,0]
[-1,0,1]
...
[0]
[0,1]
[0,1,2]
...
这种算法，时间复杂度o(n^3)
/**
* 求最大子序列和 解法一：
*/
public static void main(string[] args) {
int[] a = {-1, 0, 1, 2, -3, 8, 6};
int b = maxsum1(a);
system.out.println(b);
}
public static int maxsum1(int[] a) {
int maxsum = 0;
for (int i = 0; i < a.length ; i ) { //循环大小为n
for (int j = i; j < a.length; j ) { //循环大小为 n-i
int thissum = 0;
for (int k = i; k <= j ; k ) //循环大小为j -i 1 (求和与比较放在一个循环也是ok的，这里分开了，只求和)
thissum = a[k];
if (thissum > maxsum) {
maxsum = thissum;
}
}
}
return maxsum;
}
算法二：
这个只是对算法一进行了一些优化：
这种算法，时间复杂度o(n^2)
这里i 表示的序列的开始位置，不断推进开始位置，依次计算每个序列和，并把每轮求解的与最大值比较，把大于最大值的
当前值赋值给最大值。
public static int maxsum2(int[] a) {
int maxsum = 0;
for (int i = 0; i < a.length ; i ) {
int thissum = 0;
for (int j = i; j < a.length; j ) {
thissum = a[j];
if (thissum > maxsum) {
maxsum = thissum;
}
}
}
return maxsum;
}
算法四：
时间复杂度：o（n）
思想分析：
要求解序列中最大的和，那么需要得到，每个序列的和，并比较值
int[] a = {-1, 0, 1, 2, -3, 8, 6};
因为 -1, 0, 1, 2, -3 的 和 <0 因此序列的开始位置可以从
8 开始
这个算法中，对算法三进行了优化，如果一个序列的和出现负值，那么可以把起始点推进到 j 1 的位置
/**
* 经典算法：这个算法只对数据进行一次扫描，一旦a[i] 被读入并处理，就不需要被记忆，
* 因此，如果数组在磁盘上或通过互联网传送，那么它就可以按顺序读入，在主存中不必存
* 储数组的任何部分。
* 并且在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。（这种算法叫作联机算法）
*
* @param a
* @return
*/
public static int maxsubsum4(int[] a) {
int maxsum = 0,thissum = 0;
for (int j = 0; j < a.length; j ) {
thissum = a[j];
if (thissum > maxsum) {
maxsum = thissum;
} else if (thissum < 0) {
thissum = 0;
}
}
return maxsum;
}