0001 extern int s_lo, s_hi;
0002 
0003 int gs_DC( int A[], int lo, int hi ) { //分治策略：O(n*logn)
0004    if ( hi - lo < 2 ) return A[lo];
0005    int mi = (lo + hi) / 2;
0006 
0007    int gsL = A[mi-1], sL = 0, i = mi; //枚举
0008    while ( lo < i-- ) //所有[i, mi)类区段
0009       if ( gsL < (sL += A[i]) ) gsL = sL;
0010 
0011    int gsR = A[mi], sR = 0, j = mi-1; //枚举
0012    while ( ++j < hi ) //所有[mi, j)类区段
0013       if ( gsR < (sR += A[j]) ) gsR = sR; //择优、更新
0014 
0015    return max( gsL + gsR, max( gs_DC( A, lo, mi ), gs_DC( A, mi, hi ) ) ); //递归
0016 }