動态規劃練習——最大子矩陣

題目要求：

已知矩陣的大小定義為矩陣中所有元素的和。給定一個矩陣，你的任務是找到最大的非空(大小至少是1 * 1)子矩陣。

比如，如下4 * 4的矩陣

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

的最大子矩陣是

9 2

-4 1

-1 8

這個子矩陣的大小是15。

題目思路：

将矩陣的每一列壓縮成一行，對壓縮成的一行求最大子序列，利用循環求每行開始壓縮後所得的最大子序列的值，最終得到的最大值則為最大子矩陣的值。

細節處理：

對每行開始往下壓縮進行求值，求出所有的可能性。

#include<bits/stdc++.h>
using namespace std;
int s(int b[],int N)
{
        int c=0,max=0,i;
        for(i=1;i<=N;i++)
          {if(c>0)
            c+=b[i];
        else c=b[i];
        if(max<c)
            max=c;}
            return max;

}
int main()
{   //freopen("d://data.in","r",stdin);
    int a[105][105],b[105];
    int N,n=1,i,j,k,sum,max=0;
    cin>>N;
    for(i=1;i<=N;i++)
    {
        for(j=1;j<=N;j++)
        cin>>a[i][j];}
    while(n<=N)
    {for(j=1;j<=N;j++)
        b[j]=0;
        for(j=n;j<=N;j++)
        {
            for(k=1;k<=N;k++)
            b[k]+=a[j][k];
    sum=s(b,N);
    if(max<sum)
        max=sum;
        }
        n++;}

    cout<<max<<endl;
    return 0;
}
           

感悟：對于二維數組的問題可以考慮轉化成一位數組進行求值。