0001 #include <cstdlib>
0002 #include <ctime>
0003 #include <cstdio>
0004 
0005 int s_lo, s_hi;
0006 
0007 int gs_LS(int A[], int n); //扫描策略：O(n)
0008 int gs_DC(int A[], int lo, int hi); //分治策略：O(n*logn)
0009 int gs_IC(int A[], int n); //递增策略：O(n^2)
0010 int gs_BF(int A[], int n); //蛮力策略：O(n^3)
0011 
0012 int main(int argc, char* argv[]) { //最大片段
0013    int* A; int n;
0014    if (1 < argc) { //命令行指定：-123 89 -86 -50 -63 88 -56 -5 31 112 106 72 17 127 -92 76 124 24 -54 19 -93 121 -28 11 24 -56 92 57 -16
0015       n = argc-1; A = new int[n];
0016       for (int i = 0; i < n; i++)
0017          A[i] = atoi(argv[i+1]);
0018    } else { //随机生成
0019       srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0020       n = rand() % 128; A = new int[n];
0021       for (int i = 0; i < n; i++)
0022          A[i] = rand() % 128 - rand() % 96;
0023    }
0024    for (int i = 0; i < n; i++)
0025       printf("%3d:%4d\n", i, A[i]);
0026    printf("GreatestSlice by Linear Scan:\t\t%d", gs_LS(A, n)); printf(" @[%d,%d)\n", s_lo, s_hi);
0027    printf("GreatestSlice by Divide-And-Conquer:\t%d\n", gs_DC(A, 0, n));
0028    printf("GreatestSlice by Incremental:\t\t%d", gs_IC(A, n)); printf(" @[%d,%d)\n", s_lo, s_hi);
0029    printf("GreatestSlice by Brute-Force:\t\t%d", gs_BF(A, n)); printf(" @[%d,%d)\n", s_lo, s_hi);
0030    delete[] A;
0031    return 0;
0032 }