题目链接：http://poj.org/problem?id=1050
题目大意：求一个最大为100*100矩阵中的子矩阵中元素之和的最大值。

枚举此子矩阵是第i行到第j行。然后压成一维dp最大子段和。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;

//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

int m[105][105];
int s[105][105];

int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        memset(s[0], 0, sizeof(s[0]));

        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&m[i][j]);
                s[i][j]=s[i-1][j]+m[i][j];
            }
        }

        int MAX=-1000;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=n;j++)
            {
                int dp[105]={0};
                for(int k=1;k<=n;k++)
                {
                    int x=s[j][k]-s[i-1][k];
                    dp[k]=max(dp[k-1]+x, x);
                    MAX=max(MAX, dp[k]);
                }
            }
        }
        cout<<MAX<<endl;

    }

    return 0;
}