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; s_lo = 0; s_hi = 1;
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 }