最大连续子序列之和问题

(源自算法分析课件)

长度为n的数组有n²个子序列，长度为n的序列求和时间复杂度为O(n)，这样穷举求解的方法是与本题无关的，呵呵。

 1 int maxSubSequenceSum( int a[ ], int n )
 2 {
 3 　　maxSum = 0;
 4 　　subSum = 0;
 5 　　
 6 　　for ( j = 0; j<n; j++ ) // i 是subSum的起始位置，j 是subSum的结束位置
 7 　　{ 
 8 　　　　subSum += a[ j ];  /*　subSum是从始至终一直在累加的，当为负时归0。
 9 　　　　　　　　　　　　　　　　而maxSum就是整个过程中subSum最大的值。
10 　　　　　　　　　　　　　　　　算法的思想是：subSum是从前往后递进的子序列和，
11 　　　　　　　　　　　　　　　　只要subSum为正，它对后面的子序列的和都是起积极作用的，
12 　　　　　　　　　　　　　　　　为负时起消极作用，所以subSum归0 。*/
13 　　　　if ( subSum > maxSum ) //刷新最大值
14 　　 　　　  maxSum = subSum;
15 　　　　else
16 　　　　　　if ( subSum < 0 ) //过滤累加负值部分
17 　　　　　　　 subSum = 0;
18 　　}
19 　　return maxSum;
20 }