欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求数组连续元素的最大和和矩阵子矩阵的最大和

程序员文章站 2022-05-22 13:58:19
...
1,
给定一个长度为n的一维数组a,请找出此数组的一个子数组,使得此子数组的
和sum=a[i]+a[i+1]+……+a[j]最大,其中i>=0,i<n,j>=i,j<n,
例如 31 -41 59 26 -53 58 97 -93 -23 84
子矩阵59+26-53+58+97=187为所求的最大子数组。
实例代码:

#include <iostream>
using namespace std ;

//直接穷举法,求出所有可能的组合和 O(N^3)
int getSum1(int a[],int N)
{
int max=-10000000;
for(int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
int tmp=0;
for(int k=i;k<=j;k++)
tmp+=a[k];
if(tmp>max)
max=tmp;
}
}
return max;
}

//带记忆的递推法 O(N^2)
int getSum2(int a[],int N)
{
int* cumarr=new int[N];
cumarr[0]=a[0];
//预处理,使得求组合的和更容易
for(int i=0;i<N;i++)//首先生成一些部分和
{
cumarr[i]=cumarr[i-1]+a[i];
}
int max=-10000000;

for(int i=0;i<N;i++)
{
for(int j=i;j<N;j++)
{
//优化的地方
int tmp=cumarr[j]=cumarr[i];
if(tmp>max)
max=tmp;
}
}
delete[] cumarr;
return max;
}

//第三种,
int maxSubArray(int a[],int N)
{
int b=0,max=-10000000;
for(int i=0;i<N;i++)
{
if(b>0) b+=a[i]; //大于0,则将之前的累加
else b=a[i];
if(b>max) max=b;
}
return max;
}


int main ()
{
int a[]={31,-41,59,26,-53,58,97,-93,-23, 84};
int N=sizeof(a)/sizeof(a[0]);
cout<<getSum1(a,N)<<endl;
cout<<getSum1(a,N)<<endl;
cout<<maxSubArray(a,N)<<endl;
return 0 ;
}


2,
相关标签: J#