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 int gsL = A[mi-1], sL = 0, i = mi; //枚举 0021 while ( lo < i-- ) //所有[i, mi)类区段 0022 if ( gsL < (sL += A[i]) ) gsL = sL; 0023 int gsR = A[mi], sR = 0, j = mi - 1; //枚举 0024 while ( ++j < hi ) //所有[mi, j)类区段 0025 if ( gsR < (sR += A[j]) ) gsR = sR; //择优、更新 0026 return __max( gsL + gsR, __max( gs_DC( A, lo, mi ), gs_DC( A, mi, hi ) ) ); //递归 0027 } 0028 0029 int gs_IC( int A[], int n ) { //递增策略:O(n^2) 0030 int gs = A[0]; s_lo = n; s_hi = -1; 0031 for ( int i = 0; i < n; i++ ) { //枚举所有起始于i 0032 int s = 0; 0033 for ( int j = i; j < n; j++ ) { //终止于j的区间 0034 s += A[j]; //递增地得到其总和:O(1) 0035 if ( gs < s ) { gs = s; s_lo = i; s_hi = j + 1; } //择优、更新 0036 } 0037 } 0038 return gs; 0039 } 0040 0041 int gs_BF( int A[], int n ) { //蛮力策略:O(n^3) 0042 int gs = A[0]; s_lo = n; s_hi = -1; 0043 for ( int i = 0; i < n; i++ ) 0044 for ( int j = i; j < n; j++ ) { //枚举所有的O(n^2)个区段 0045 int s = 0; for ( int k = i; k <= j; k++ ) s += A[k]; //用O(n)时间求和 0046 if ( gs < s ) { gs = s; s_lo = i; s_hi = j + 1; } //择优、更新 0047 } 0048 return gs; 0049 } 0050 0051 /****************************************************************************************** 0052 * 最大片段 0053 ******************************************************************************************/ 0054 int main ( int argc, char* argv[] ) { 0055 int* A; int n; 0056 if ( 1 < argc ) { //命令行制定 0057 n = argc - 1; A = new int[n]; 0058 for ( int i = 0; i < n; i++ ) { 0059 A[i] = atoi( argv[i+1] ); 0060 printf("%d\t%s\t%d\n", i, argv[i+1], A[i]); 0061 } 0062 } else { //随机生成 0063 srand ( ( unsigned int ) time ( NULL ) ); 0064 n = rand() % 128; A = new int[n]; 0065 for ( int i = 0; i < n; i++ ) { 0066 A[i] = rand() % 128 - rand() % 96; 0067 printf("%d\t%d\n", i, A[i]); 0068 } 0069 } 0070 printf( "GS by Linear Scan:\t\t%d", gs_LS( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0071 printf( "GS by Divide-And-Conquer:\t%d\n", gs_DC( A, 0, n ) ); 0072 printf( "GS by Incremental:\t\t%d", gs_IC( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0073 printf( "GS by Brute-Force:\t\t%d", gs_BF( A, n ) ); printf( "\t%d\t%d\n", s_lo, s_hi ); 0074 delete [] A; 0075 return 0; 0076 }