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 /******************************************************************************************
0013  * 最大片段
0014  ******************************************************************************************/
0015 int main ( int argc, char* argv[] ) {
0016    int* A; int n;
0017    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
0018       n = argc-1; A = new int[n];
0019       for ( int i = 0; i < n; i++ )
0020          A[i] = atoi( argv[i+1] );
0021    } else { //随机生成
0022       srand ( ( unsigned int ) time ( NULL ) );
0023       n = rand() % 128; A = new int[n];
0024       for ( int i = 0; i < n; i++ )
0025          A[i] = rand() % 128 - rand() % 96;
0026    }
0027    for ( int i = 0; i < n; i++ )
0028       printf("%3d:%4d\n", i, A[i]);
0029    printf( "GreatestSlice by Linear Scan:\t\t%d", gs_LS( A, n ) ); printf( " @[%d,%d)\n", s_lo, s_hi );
0030    printf( "GreatestSlice by Divide-And-Conquer:\t%d\n", gs_DC( A, 0, n ) );
0031    printf( "GreatestSlice by Incremental:\t\t%d", gs_IC( A, n ) ); printf( " @[%d,%d)\n", s_lo, s_hi );
0032    printf( "GreatestSlice by Brute-Force:\t\t%d", gs_BF( A, n ) ); printf( " @[%d,%d)\n", s_lo, s_hi );
0033    delete [] A;
0034    return 0;
0035 }