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.
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 the sum of the maximal sub-rectangle.
Greater New York 2001
http://poj.org/problem?id=1050
最大子矩阵问题
给定一个n*n(0<n<=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
首先先了解下求最大子段和问题
问题描述： 给定n个整数（可能为负整数）组成的序列a1,a2,a3……an。求该序列如同的子段和的最大值
#include <stdio.h> //N是数组长度，num是待计算的数组，放在全局区是因为可以开很大的数组 int N, num[134217728]; int main() { //输入数据 scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d", &num[i]); num[0] = 0; int ans = num[1]; for(int i = 1; i <= N; i++) { if(num[i - 1] > 0) num[i] += num[i - 1]; else num[i] += 0; if(num[i] > ans) ans = num[i]; } printf("%d\n", ans); return 0; }这个题和上面的解体思路类似，我们可以把二维变成一维，把下面每一行加到上一行中对应列中。
例如：
a11 a12 a13 a21 a22 a23 a31 a32 a33
先求第一行最大子段和，再求第一行跟第二行合起来的最大子段和，如a21+a11, a22+a12, a23+a13 的最大子段和，再求第一到第三合起来的最大子段和，如a11+a21+a31, a12+a22+a32, a13+a23+a33的最大子段和……以此类推，直到求出整个矩阵的合起来的最大子段和，求出他们之中最大的那个和就是解.
