今晚搞了很久各种电脑，最后亲亲断网了才开起电脑，于是在POJ找了道简单的题目做，看了POJ1050通过率50%多，想着应该用不了多久，就准备做这个了。

Description

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:

9 2
-4 1
-1 8
and has a sum of 15.

Input

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Output

Output the sum of the maximal sub-rectangle.

Sample Input

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

8  0 -2

Sample Output

15

初看题目，第一感觉是直接枚举，复杂度是1亿级别的……显然不行，仔细想想，发现可以做一个优化，直接开两个数组，在100100100的时间里面可以算出同一行或者同一列任意两个点范围内的和，这两个数组显然可以让题目做出来方便很多，但是枚举估计还是不行。再想想，题目应该可以动规，a[i][j][k]表示左边界为k的情况下，右下角点为i,j时所能达到的最大值。递推方程找到了。于是开工。具体写的时候思路很混乱……i,j,k具体表示什么搞得越来越糊涂，最后写递推的时候发现预处理出来的两个和数组只需要用一个，先用了其中一个，发现答案不对，于是另外一个，样例答案对了，直接提交，MLE……悲剧……发现内存只有10M,于是删掉不用的那个数组，提交,WA了……大悲剧……不过也在意料之中，因为思路太混乱了……自己想到个特殊情况的测试数据，3*3的矩阵全是-1，测试了一下，发现不能过。于是就开始检查，越检查发现思路越混乱……于是拿了张纸把数组具体表示什么仔仔细细的写下来……终于思路清晰了……修改了一下程序，终于过了……

最近一直没做题目的关系吧……思路太混乱了……多练练应该会好点……还有把思路写下来确实挺有效的……话说以前写程序都不用这样子的……悲剧……