0001 #include <stdlib.h> 0002 #include <time.h> 0003 #include <stdio.h> 0004 0005 int s_lo, s_hi; 0006 0007 int gs_LS( int A[], int n ) { //扫描策略:O(n) 0008 int gs = A[0], s = 0, i = n, j = n; 0009 while ( 0 < i-- ) { //对于当前区间[i,j) 0010 s += A[i]; //递增地得到其总和:O(1) 0011 if ( gs < s ) { gs = s; s_lo = i; s_hi = j; } //择优、更新 0012 if ( s <= 0 ) { s = 0; j = i; } //剪除负和后缀 0013 } 0014 return gs; 0015 } 0016 0017 int gs_DC( int A[], int lo, int hi ) { //分治策略:O(n*logn) 0018 if ( hi - lo < 2 ) return A[lo]; 0019 int mi = (lo + hi) / 2; 0020 0021 int gsL = A[mi-1], sL = 0, i = mi; //枚举 0022 while ( lo < i-- ) //所有[i, mi)类区段 0023 if ( gsL < (sL += A[i]) ) gsL = sL; 0024 0025 int gsR = A[mi], sR = 0, j = mi-1; //枚举 0026 while ( ++j < hi ) //所有[mi, j)类区段 0027 if ( gsR < (sR += A[j]) ) gsR = sR; //择优、更新 0028 0029 return __max( gsL + gsR, __max( gs_DC( A, lo, mi ), gs_DC( A, mi, hi ) ) ); //递归 0030 } 0031 0032 int gs_IC( int A[], int n ) { //递增策略:O(n^2) 0033 int gs = A[0]; s_lo = n; s_hi = -1; 0034 for ( int i = 0; i < n; i++ ) { //枚举所有起始于i 0035 int s = 0; 0036 for ( int j = i; j < n; j++ ) { //终止于j的区间 0037 s += A[j]; //递增地得到其总和:O(1) 0038 if ( gs < s ) { gs = s; s_lo = i; s_hi = j + 1; } //择优、更新 0039 } 0040 } 0041 return gs; 0042 } 0043 0044 int gs_BF( int A[], int n ) { //蛮力策略:O(n^3) 0045 int gs = A[0]; s_lo = n; s_hi = -1; 0046 for ( int i = 0; i < n; i++ ) 0047 for ( int j = i; j < n; j++ ) { //枚举所有的O(n^2)个区段 0048 int s = 0; for ( int k = i; k <= j; k++ ) s += A[k]; //用O(n)时间求和 0049 if ( gs < s ) { gs = s; s_lo = i; s_hi = j + 1; } //择优、更新 0050 } 0051 return gs; 0052 } 0053 0054 /****************************************************************************************** 0055 * 最大片段 0056 ******************************************************************************************/ 0057 int main ( int argc, char* argv[] ) { 0058 int* A; int n; 0059 if ( 1 < argc ) { //命令行制定 0060 n = argc-1; A = new int[n]; 0061 for ( int i = 0; i < n; i++ ) { 0062 A[i] = atoi( argv[i+1] ); 0063 printf("%d\t%s\t%d\n", i, argv[i+1], A[i]); 0064 } 0065 } else { //随机生成 0066 srand ( ( unsigned int ) time ( NULL ) ); 0067 n = rand() % 128; A = new int[n]; 0068 for ( int i = 0; i < n; i++ ) { 0069 A[i] = rand() % 128 - rand() % 96; 0070 printf("%d\t%d\n", i, A[i]); 0071 } 0072 } 0073 printf( "GS by Linear Scan:\t\t%d", gs_LS( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0074 printf( "GS by Divide-And-Conquer:\t%d\n", gs_DC( A, 0, n ) ); 0075 printf( "GS by Incremental:\t\t%d", gs_IC( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0076 printf( "GS by Brute-Force:\t\t%d", gs_BF( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0077 delete [] A; 0078 return 0; 0079 }