0001 extern int s_lo, s_hi; 0002 0003 int gs_LS( int A[], int n ) { //扫描策略:O(n) 0004 int gs = A[0], s = 0, i = n, j = n; 0005 while ( 0 < i-- ) { //在当前区间[i,j)内 0006 s += A[i]; //递增地累计总和 0007 if ( gs < s ) { gs = s; s_lo = i; s_hi = j; } //择优、更新 0008 if ( s <= 0 ) { s = 0; j = i; } //剪除负和后缀 0009 } 0010 return gs; 0011 }