题目名称：To the Max

题目来源：POJ 1050

题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

题目分类：动态规划

解题思路：

题目要求清晰，求出最大子矩阵。其中，输入数据是一个N*N的矩阵。

（1）化简为一维情况

    矩阵是二维的，先把这个问题简化，如果变成一维的情况如何？即对于形如 1 -2 3 4 7 的这一行求最大子段问题，对于这个一维情况，容易知道如下的规律：
   

    若记b[j]为从a[i]到a[j]的最大的子段和（j是定的，“最大”指的是i从1到j-1中，a[i]+...+a[j]最大的），那么所求的max{ a[i]+a[i+1]+...+a[j-1]+a[j] (1<=i<j<=n) }＝max{ max{ a[i]+..+a[j] (1<=j<=n) } }＝max{ b[1]+...+b[n] }。

b[]由定义可知：j==1时，b[1]=a[1]；j>1时,b[j]=max{ b[j-1]+a[j],a[j] }。

实际上，这个一维情况可以继续化简，即b[j] = (b[j-1]>0?b[j-1]:0)+a[j]

（2）从一维到二维

    一维的情况很简单，如何把一维的情况转化为二维情况呢？

例如，对于本题的测试数据：

我们可以每次任选几行，压缩成一行，这样就转化为了一维情况。

例如，我们求1~2行中的最大子矩阵：即矩阵高为2（1~2行），宽为1：4的矩阵，可以先把1~2行相加，得到9 0 -13 2，再求这个单行的最大子段，由此就可以求得1~2行的最大子矩阵。

依次类推，我们需要求得所有的高为1、2、3、4的矩阵，即

高为1的：

0 -2 -7 0   和 9   2 -6   2 和 -4 1 -4 1 和 -1 8 0 -2

高为2的：1~2行，2~3行 3~4行

。。。。。

因为这是一个Cn的组合问题，所以我们可以设置两个变量i，j，每次选择从i到j的行，压缩成一行，然后求这一行的最大字段。其中，i，j为两层循环分别为从1~N

（3）程序

#include <iostream>
using namespace std;

int rect[101][101];

int maxvalue;

//思想：先压缩到一行，然后横向DP
//横向DP 递推公式 maxn[i]=max{0,maxn[i-1]}+a[i];
void dp(int n)
{
int line[101];//压缩到一行的数据

for(int i=1;i<=n;i++)
{
   for(int j=1;j<=n;j++)
   {

    //把第i到j行压缩成一行
    memset(line,0,sizeof(line));
    for(int row = i;row<=j;row++)
    {

     for(int col = 1;col<=n;col++)
     {
      line[col]+=rect[row][col];
     }
    }//end 把第i到j行压缩成一行
   
    //至此，line[1:n]变成了一维的最长子序列
    for(int i=2;i<=n;i++)
    {
     line[i] = (line[i-1]>0?line[i-1]:0)+line[i];

     if(line[i]>maxvalue)
     {
      maxvalue = line[i];
     }
    }

   }//end for j
}//end for i

}

int main()
{
int n;

while(cin>>n)
{
   //数据输入
   for(int i=1;i<=n;i++)
   {
    for(int j=1;j<=n;j++)
    {
     cin>>rect[i][j];
    }
   }
  
   maxvalue = 0;
   dp(n);
  
   cout<<maxvalue<<endl;
}

return 0;

}