1074 To the Max

  这是一道比较经典的动态规划的例题，感觉思路挺巧。这里有一篇不错的文章，可以看一下：

   http://blog.csdn.net/piaoyi0208/article/details/7728972

  还有关于动态规划入门的一篇文章：http://blog.csdn.net/jqandjq/article/details/5060283

#include <iostream>
#include <cstring>
using namespace std;
int n,i,j,k,l,i_max;
int array[101][101],sum[101];
int main()
{
    while(cin>>n)
    {
        i_max=-10000000;
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
          {cin>>array[i][j];
           if(array[i][j]>i_max) i_max=array[i][j];
          }
        for(i=0;i<n;i++)//从第i行到后面j行的数相加，形成新的一行。也就是从多维到一维的转换 
          for(j=0;j<=n-i-1;j++)
           {
                memset(sum,0,sizeof(sum));
                for(k=i;k<=i+j;k++)//从i行到j行相加 
                  for(l=0;l<n;l++)
                    {
                        sum[l]+=array[k][l];
                        if(sum[l]>i_max) i_max=sum[l];
                    }
                    for(l=1;l<n;l++)//动态规划求最大值 
                     {
                         if(sum[l-1]>0) sum[l]+=sum[l-1];
                         if(sum[l]>i_max) i_max=sum[l];
                     }
           }
     cout<<i_max<<endl;
     }
    
    return 0;
}