求一个向量的任何连续子向量的最大和
比如向量(31,-41,59,26,-53,58,97,-93,-23,84);
最大和是从59到97即为187
#include<stdio.h> #include<stdlib.h> //两者的最大值 int max( int x, int y ); //三者的最大值 int max2( int x, int y, int z ); //最原始的算法，复杂度为T(n)=O(n*n) int oringinal( int v[], int len ); //原始基础上变体版,复杂度为T(n)=O(n*n) int oringinal_ex( int v[], int len ); //分治法,复杂度为T(n)=O(n*log(n)) /* *分治法的思想是：将原数组分成两部分，要求的最大值 *要么在左边这部分里面，要么在右边这部分里面 *要么就在左右相交的交界处 */ int divAndCon( int v[], int low, int high ); //扫描法,复杂度为T(n)=O(n) int scan(int v[], int len); void main() { int i = 0; int v[] = {31,-41,59,26,-53,58,97,-93,-23,84}; int len = 0; int result; len = sizeof(v) / sizeof(int); printf("oringinal datas:n"); for( i = 0; i < len; i++ ) { printf("%dt",v[i]); } printf("n"); //最原始的算法 result = oringinal(v,len); printf("oringinal(v,len):%dn",result); //最原始变体的算法 result = oringinal_ex(v,len); printf("oringinal_ex(v,len):%dn",result); //分治法 result = divAndCon(v,0,len-1); printf("divAndCon(v,0,len):%dn",result); //扫描法 result = scan(v,len); printf("scan(v,len):%dn",result); } //两者的最大值 int max( int x, int y ) { if( x < y ) { x = y; } return x; } //三者的最大值 int max2( int x, int y, int z ) { if( x < y ) { x = y; } if( x < z ) { x = z; } return x; } //最原始的算法，复杂度为T(n)=O(n*n) int oringinal( int v[], int len ) { int maxsofar = 0; int i; int j; int sum = 0; //通过双层循环逐步扫描，通过max( sum, maxsofar)获得当前最大值 for( i = 0; i < len; i++ ) { sum = 0; for( j = i; j < len; j++ ) { sum += v[j]; maxsofar = max( sum, maxsofar ); } } return maxsofar; } //原始基础上变体版,复杂度为T(n)=O(n*n) int oringinal_ex( int v[], int len ) { int i = 0; int j = 0; int sum = 0; int maxsofar = 0; int *cumarr = ( int * )malloc( len * sizeof(int) ); for( i = 0; i < len; i++ ) { if( i == 0 ) { cumarr[0] = v[i]; } else { cumarr[i] = cumarr[i-1] + v[i]; } } for( i = 0; i < len; i++ ) for( j = i; j < len; j++ ) { if( i == 0 ) { sum = cumarr[i]; } else { sum = cumarr[j] - cumarr[i-1]; } maxsofar = max(maxsofar,sum); } return maxsofar; } //分治法,复杂度为T(n)=O(n*log(n)) int divAndCon( int v[], int low, int high ) { int mid = 0; int lmax = 0; int rmax = 0; int sum = 0; int i = 0; if( low > high ) { return 0; } if( low == high ) { return max(0,v[low]); } mid = ( low + high ) / 2; lmax = sum = 0; for( i = mid; i >= low; i-- ) { sum += v[i]; lmax = max(lmax,sum); } rmax = sum = 0; for( i = mid + 1; i <= high; i++ ) { sum +=v[i]; rmax = max(rmax,sum); } return max2(lmax + rmax,divAndCon(v,low,mid),divAndCon(v,mid+1,high)); } //扫描法,复杂度为T(n)=O(n) int scan(int v[], int len) { int maxsofar = 0; int maxendinghere = 0; int i = 0; for( i =0; i < len; i++ ) { maxendinghere = max(maxendinghere + v[i],0); maxsofar = max(maxsofar,maxendinghere); } return maxsofar; }
求一个向量的任何连续最接近0的子向量的和
比如向量(31,-41,59,26,-53,58,97,-93,-23,84);
最大和是从97到-93即为4
#include<stdio.h> #include<math.h> //返回最接近0的数 int closeZero( int x, int y ); //最原始的算法，复杂度为T(n)=O(n*n) int oringinal( int v[], int len ); void main() { int i = 0; int v[] = {31,-41,59,26,-53,58,97,-93,-23,84}; int len = 0; int result; len = sizeof(v) / sizeof(int); printf("oringinal datas:n"); for( i = 0; i < len; i++ ) { printf("%dt",v[i]); } printf("n"); //最原始的算法 result = oringinal(v,len); printf("oringinal(v,len):%dn",result); } //返回最接近0的数 int closeZero( int x, int y ) { if( abs(x) > abs(y) ) { x = y; } return x; } //最原始的算法，复杂度为T(n)=O(n*n) int oringinal( int v[], int len ) { int sofar = v[0]; int i; int j; int sum = 0; for( i = 0; i < len; i++ ) { sum = 0; for( j = i; j < len; j++ ) { sum += v[j]; sofar = closeZero( sum, sofar ); } } return sofar; }
运行结果：
