poj1050 To the Max

不知道最大子矩阵跟贪心有什么关系。。。

写过好多次了gugugu。贴一个网上贪心的题解。。。O（n^2）的悬线，单调栈不好吗。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[200][200],f[200];
int main(){
    //freopen("in.txt","r",stdin);
    int n,i,x,y,k,j,maxn=-1e6;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++){
        scanf("%d",&a[i][j]);
    }
    for(k=1;k<=n;k++){//矩阵大小 
    for(i=1;i<=n-k+1;i++){ //起始行 
    memset(f,0,sizeof(f));//每找一个矩阵先清零 
    for(j=1;j<=n;j++){//循环列 
        for(x=i;x<=i+k;x++)f[j]+=a[x][j];//处理每一列的值 
        f[j]=max(f[j],f[j-1]+f[j]);
        if(f[j]>maxn)maxn=f[j];
    }}}
    printf("%d",maxn);
    return 0;
}