0001 int gs_LS(int A[], int n) { //减治策略：O(n)
0002    int gs = 0; //目前已知的最大和 = S[n,n) = 0
0003    for (int sum = 0, k = n-1; 0 <= k; k--) { //自后向前，逐个地考查后缀[k,n)
0004       sum += A[k]; //递增地更新后缀和
0005       gs = max(gs, sum); //择优更新（若gs增大，则可同时更新GS的左、右端点）
0006       sum = max(sum, 0); //若S[k,n)非正，则剪除该后缀（接下来考查以n=k为终点的后缀）
0007    } //for
0008    return gs;
0009 } //gs_LS