一，问题描述
给定（可能有负数）整数a(1)、a(2)、……a(n)，求 a(1)+a(2)+……+a(j)的最大值。为方便起见，若所有的整数为负数，则最大子序列和为0.
也就是：在一系列整数中，找出连续的若干个整数，这若干个整数之和 最大。
二，求解思路
下面介绍两种思路，一种的时间复杂度为O(N^3)，另一种为O(N)。这两种方法分别类似于 在O(N)时间内求解 正数数组中 两个数相加的 最大值 和 两种方法求解 正数数组中 两个数相减 的最大值
里面介绍的O(N^2)算法和 O(N)算法。都是采用了“贪心”的思想 忽略掉某些不需要判断的元素，如本文中算法二：总是选择，使当前序列之和变成负数的下一个元素作为新的起点。
因此，可以看出，最大子序列和问题 其实 与寻找“正整数数组中两个数相减的最大值” 、“正整数数组中两个数相加的最大值”等问题很相似。
算法一如下：
分别用两个下标 i , j 标记某个子序列的起点和终点。然后，从 i 遍历 到 j，求出[i,j]内所有元素的和，这个 和值 就是这一段子序列的和。
i belongs to [0, arr.length) , j belongs to [i, arr.length) 这样，就代表了所有的子序列，再找出所有子序列和的最大值。
代码如下：
1 public static int maxSubSum1(int[] arr) {
2 int maxSum = 0;
3
4 for (int i = 0; i < arr.length; i++)
5 for (int j = i; j < arr.length; j++) {
6 int thisSum = 0;
7 for (int k = i; k <= j; k++)
8 thisSum += arr[k];// 求解[i,j]这段子序列的和
9 if (thisSum > maxSum)
10 maxSum = thisSum;
11 }
12 return maxSum;
13 } 算法二如下：
算法二基于下面两个事实：
①任何负的 子序列都不可能是最大子序列和 的前缀
②当加上 下标 j 所在的元素 使得 当前序列的和变成负数时，根据①，可以从 j+1 处重新开始计算下一段子序列的和。
因为某段子序列到索引 j 位置时，它们的和是负的，意味着最大子序列不会 包含这一段子序列，那么从 j+1 开始，能不能找到一段更大的子序列。
1 public static int maxSubSum2(int[] arr) {
2 int maxSum = 0;
3 int thisSum = 0;
4 for (int i = 0; i < arr.length; i++) {
5 thisSum += arr[i];
6 if (thisSum > maxSum)// thisSum在[0,maxSum]之间时不需要任何处理
7 maxSum = thisSum;
8 else if (thisSum < 0)// 说明加上当前元素使得子序列为负数了,那么抛弃这段子序列(相当于thisSum赋值为0),从下一轮for开始
9 thisSum = 0;
10 }
11 return maxSum;
12 } 三，运行时间的比较
采用 这篇文章 中提到的随机数生成算法 来随机生成一个数组，然后比较上面两个算法的运行时间。
机器环境如下：
OS:win7 64bit、RAM:6GB、CPU:Pentium(R)Dual-Core [email protected]
时间比较如下：
数组大小 maxSubSum1运行时间(O(N)) maxSubSum2算法2运行时间(O(N^3))
100*10 0 95
200*10 0 647
300*10 0 2128
400*10 0 40246
这就是差距。。。。。。
完整程序代码如下：
1 public class MaxSequence {
2
3 public static int maxSubSum1(int[] arr) {
4 int maxSum = 0;
5
6 for (int i = 0; i < arr.length; i++)
7 for (int j = i; j < arr.length; j++) {
8 int thisSum = 0;
9 for (int k = i; k <= j; k++)
10 thisSum += arr[k];// 求解[i,j]这段子序列的和
11 if (thisSum > maxSum)
12 maxSum = thisSum;
13 }
14 return maxSum;
15 }
16
17 public static int maxSubSum2(int[] arr) {
18 int maxSum = 0;
19 int thisSum = 0;
20 for (int i = 0; i < arr.length; i++) {
21 thisSum += arr[i];
22 if (thisSum > maxSum)// thisSum在[0,maxSum]之间时不需要任何处理
23 maxSum = thisSum;
24 else if (thisSum < 0)// 说明加上当前元素使得子序列为负数了,那么抛弃这段子序列(相当于thisSum赋值为0),从下一轮for开始
25 thisSum = 0;
26 }
27 return maxSum;
28 }
29
30 public static void main(String[] args) {
31 int[] arr = C2_2_8.randomArr(100*80);
32
33 long start = System.currentTimeMillis();
34 int r = maxSubSum2(arr);
35 long end = System.currentTimeMillis();
36 System.out.println("maxValue=" + r + " O(N)'s time:" + (end - start));
37
38 long start2 = System.currentTimeMillis();
39 int r2 = maxSubSum1(arr);
40 long end2 = System.currentTimeMillis();
41 System.out.println("maxValue=" + r2 + " O(N^3)'s time:"
42 + (end2 - start2));
43
44 }
45 }