POJ1050 最大子矩陣和

第一篇題解，先來個簡單的熱熱身

POJ 1050 求最大子矩陣和 多組資料輸入 n不大于100

用 i 和 j 枚舉 子矩陣從 第i行 開始到 第j行 結束

将第k(1<=k<=n)列的數從第i行加到第j行

然後就降到一維了，現在就是一個求最大子段和了

這樣的時間複雜度為O(n^3)不知道有沒有更快的算法

代碼如下

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

int a[105][105]={0},b[105][105]={0};

int main()

{

int n,i,j,k,t,ans=0,sum=0,max1,max2;

while (scanf("%d",&n)==1)

{

memset(a,0,sizeof(a));memset(b,0,sizeof(b));max2=0;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{

scanf("%d",&a[i][j]);

b[j][i]=b[j][i-1]+a[i][j];

}

for (i=1;i<=n;i++)

for (j=i;j<=n;j++)

{

sum=0;max1=0;

for (k=1;k<=n;k++)

{

t=b[k][j]-b[k][i-1];

sum+=t;

sum=max(sum,0);

max1=max(max1,sum);

}

max2=max(max2,max1);

}

printf("%d\n",max2);

}

return 0;

}

</cstring></cmath></algorithm></cstdio>