求最大子列和

Paste_Image.png

第一种：最简单的解法：把所有子列都算一遍找到最大的

int MaxSubseqSum2( int A[], int N )  
{   int ThisSum, MaxSum = 0;
  int i, j;
  for( i = 0; i < N; i++ ) { /* i是子列左端位置 */
        ThisSum = 0;  /* ThisSum是从A[i]到A[j]的子列和 */
        for( j = i; j < N; j++ ) { /* j是子列右端位置 */
                ThisSum += A[j];        /*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*/ 
                if( ThisSum > MaxSum ) /* 如果刚得到的这个子列和更大 */
                          MaxSum = ThisSum;    /* 则更新结果 */
        } /* j循环结束 */    
   } /* i循环结束 */    
   return MaxSum;  
}

第二种：采用分治法，运用递归来解决。（使用了分治一般O(N2)的时间复杂度一般都会降到O(Nlog(N))）

Paste_Image.png

第三种：根据问题的特殊性可知，如果一直加正数，总数会一直变大。除非加到负数才会变小。

Paste_Image.png

这种时间复杂度显而易见是：(O(N))

每种处理算法的执行时间的比较：

Paste_Image.png