学步园

不过这道题还是不怎么会做。一开始我以为既然要用DP的话，那就把矩阵的某个点作为状态，但是这样一来的话，单纯依靠下一个状态是无法得到结果的，因为还有不定长的一行和一列。原来只要把二维矩阵压缩为一维数组，问题就转化为求数组的最长子串了！

参考：http://www.cnblogs.com/aiyite826/archive/2010/07/23/1784032.html

#include <iostream>
using namespace std;

int num;
int matrix[102][102];//数组从1开始
int tmp[102];//用来暂存每一列（选择不同个数）的和

int dp()//返回最大子串 
{
    int max=-(1<<30);
    int b=tmp[1];
    for(int i=2;i<=num;i++)
    {
        if(b<0) b=tmp[i];
        else b+=tmp[i];
        if(max<b) max=b;
    }
    return max;
}

int main()
{
    int max=-(1<<30);
    cin >> num;
    for(int i=1;i<=num;i++)
        for(int j=1;j<=num;j++)
            cin >> matrix[i][j];
            
    for(int i=1;i<=num;i++)//i表示从第几行开始 
    {
        memset(tmp,0,sizeof(tmp));
        for(int j=i;j<=num;j++)//j表示从第几行结束 
        {
            for(int k=1;k<=num;k++)//k表示第几列 
            {
                tmp[k]+=matrix[j][k];
            } 
            //开始算一维数组的最大子串
            int t=dp();
            if(max<t) max=t;
        }
    }
    cout << max << endl; 
}