最大子段和、最大子矩阵和、最大m子段和问题总结

int MaxSum(int n,int *a)
{
int sum = 0;
int b = 0,i;
for(i=0;i<n;i++)
{
if(b>0) b+=a[i];
else b = a[i];
if(b>sum)sum = b;
}
return sum;
}

int MaxSum2(int m,int n,int** a)
{
int sum = 0,i,j,k;
int b[105];
for(i=0;i<m;i++)
{
for(k=0;k<n;k++)
{
b[k] = 0;
}
for(j=i;j<m;j++)
{
for(k=0;k<n;k++)
{
b[k]+=a[j][k];
}
int mx = MaxSum(n,b);
if(sum<mx)sum=mx;
}
}
return sum;
}

double b[50005];
double c[50005];
int MaxSum3(int m,int n,int* a)
{
int i,j,k,mx,sum;
b[0] = 0;
c[0] = 0;
for(i=1;i<=m;i++)
{
b[i] = b[i-1] + arr[i];
c[i-1] = b[i];
mx = b[i];
for(j=i+1;j<=i+n-m;j++)
{
b[j] = b[j-1]>c[j-1]?b[j-1]+arr[j]:c[j-1]+arr[j];
c[j-1] = mx;
if(mx<b[j])
{
mx = b[j];
}
}
c[i+n-m] = mx;
}
sum = b[m];
for(k=m+1;k<=n;k++)
{
if(sum<b[k])sum=b[k];
}
return sum;
}