首页 > 代码库 > POJ_1050_最大子矩阵

POJ_1050_最大子矩阵

http://poj.org/problem?id=1050

 

这道题是最大子串的扩展,遍历过每一个子矩阵就好了,期间用了最大子串的方法。

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[105][105],temp[105];int main(){    int n,ans = 0;    scanf("%d",&n);    for(int i = 1;i <= n;i++)    {        for(int j = 1;j <= n;j++)   scanf("%d",&a[i][j]);    }    for(int i = 1;i <= n;i++)    {        memset(temp,0,sizeof(temp));        for(int j = i;j <= n;j++)        {            int sum = 0;            for(int k = 1;k <= n;k++)            {                temp[k] += a[j][k];                sum += temp[k];                ans = max(sum,ans);                if(sum < 0) sum = 0;            }        }    }    printf("%d",ans);    return 0;}

 

POJ_1050_最大子矩阵