Description
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. 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. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array.
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-hand corner and has the 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 white-space (newlines and spaces). These N 2integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on 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
The output is the sum of the maximal sub-rectangle.
题意解析：
题目比较简单，给定一个N*N的矩阵，求这个矩阵中子矩阵的最大和。譬如给定的示例中，最大的子矩阵为
| 9 | 2 | ||
| −4 | 1 | ||
| −1 | 8 |
即为15.
解题思路：
这个是一个二维的数组，求最大子矩阵和，应该要想到使用一维的最大子序列和，然后就可以将子矩阵压缩为子序列，再求解。
1）将矩阵缩为一列列，然后对这四个列进行 求最大子序列的和。
2）求一个一维的最大子序列和。
代码如下：
#include <stdio.h>
#define MAX_N 100int arr[MAX_N][MAX_N];int rowsSum[MAX_N]; //每一行的和int N;int calc(int x, int y);int main(){ //freopen("input.txt","r",stdin); scanf("%d",&N); int i = 0; int j = 0; int max = -1270000; int sum = 0; for(i=0;i<N;i++) { for(j=0;j<N;j++) { scanf(" %d",&arr[i][j]); } }for(i=0;i<N;i++)
{ for(j=i;j<N;j++) { sum = calc(i,j); //计算第i列到第j列的最大和 if(sum>max) { max = sum; } } } printf("%d\n",max); return 0;} int calc(int x, int y){ int i = 0; int j = 0; int resultValue = -1270000; int thisSum = 0; for(i=0;i<N;i++) { rowsSum[i] = 0; for(j=x;j<=y;j++) { rowsSum[i] = rowsSum[i] + arr[i][j]; } }//rowsSum表示，对于指定的列i到j，每一行的和。
//求rowsSum[]这个一维数组的最大子序列和
for(i=0;i<N;i++) { thisSum = thisSum + rowsSum[i]; if(thisSum>resultValue) { resultValue = thisSum; } if(thisSum<0) { thisSum = 0; } }return resultValue;
}