求一个向量的任何连续子向量的最大和的4种算法实现（简单实例）

川长思鸟来 2022-05-12 11:10 160阅读 0赞

//求一个向量的任何连续子向量的最大和  
/\*  
比如向量(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("%d\\t",v\[i\]);  
\}  
printf("\\n");  
//最原始的算法  
result = oringinal(v,len);  
printf("oringinal(v,len):%d\\n",result);  
//最原始变体的算法  
result = oringinal\_ex(v,len);  
printf("oringinal\_ex(v,len):%d\\n",result);  
//分治法  
result = divAndCon(v,0,len-1);  
printf("divAndCon(v,0,len):%d\\n",result);  
//扫描法  
result = scan(v,len);  
printf("scan(v,len):%d\\n",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;  
\}

![1355021643_1586.jpg][]

/\*博主寄语：如若发现错误，望指出，谢谢\*/

[1355021643_1586.jpg]: https://img-my.csdn.net/uploads/201212/09/1355021643_1586.jpg