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:

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

is in the lower left corner:

1
2
3
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

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

8  0 -2

Sample Output

1
15

题解：

刚看到这道题思路有点乱，感觉是一道二维dp，于是沉迷于推导状态转移方程；但是又感觉和求最大子数组的和有点类似。想了半天思路不清晰看了题解，原来求矩形面积就是把相邻行逐列求和，当做一维数组当成最大子数组的和问题来处理。而求最大子数组和的问题相当在该问题中，输入是一个行为1的矩阵。

此外还需要注意的以下几点：

  • poj不支持int[n]的声明，但是在devc++中该声明可以编译通过。所以遇到这样的声明，直接写成n的实际最大值；
  • 进行数组压缩的时候是一个组合问题，千万别遗漏；
  • memset在头文件string.h中；
  • 虽然题目中的样例输入很奇怪，但是cin本身就可以截断空格，所以确定了要输入多少个元素之后，逐个遍历输入就行。刚开始的我竟然想到用getline。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<string.h>
using namespace std;

long dp[100+1]={0};
int input[100+1][100+1];
int comp_ary[100+1]={0};
                
long max_seq_sum(int* seq,int n){
    dp[0]=seq[0];
    long max_sum=dp[0];
    for(int i=1;i<n;i++){
        dp[i] = dp[i-1]>0? dp[i-1]+seq[i] : seq[i];
        if(dp[i]>max_sum)
            max_sum=dp[i];
    }
    return max_sum; 
} 

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>input[i][j];
            } 
        }
        long max_sum=INT_MIN;
        long sum=0;
        for(int i=0;i<n;i++){
            memset(comp_ary,0,sizeof(comp_ary));
            for(int j=i;j<n;j++){
                for(int k=0;k<n;k++){   //这里注意 
                    comp_ary[k]+=input[j][k];
                }
                sum=max_seq_sum(comp_ary, n);
                if(sum>max_sum) max_sum=sum;            
            }
        }
        cout<<max_sum<<endl;
    }
    return 0;
}