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: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
題意：求最大的子矩陣的和
解題思路：通過循環，用b[k]數組儲存每列的和，例如當循環到第2行時，b[0]儲存的就是5。 5是怎麼來的呢？它是0+9+(-4)=5。
b[1]儲存的就是1。 -2+2+1=1
這樣求出每列的和然後同時找b[k]序列的最大子段和，不斷更新最大值，循環完之後，就可以找出最大值了.....
也許這樣比較抽象，舉個栗子：（這裡就不用N行N列的做例子了.....）
2維數組：
1 2 3
-5 6 7
我們先求
第0行 b數組 1 2 3
最大子段和：1+2+3=6 這裡可以理解為 這是 1 2 3 這個子矩陣
第1行
b數組 -4 8 10
最大子段和：8+10=18 這裡就是 2 3
6 7 這個子矩陣
所以答案就是18
怎麼說，思想應該是通過求每列的和，使得它變成一個求最大字段和的問題.........
代碼如下：（去掉注釋，也許會對理解思路有幫助....）
1 #include<stdio.h>
2 #include <limits>
3 #include<string.h>
4 using namespace std;
5 int a[105][105],b[105];
6 int n,cursum=-130,max=numeric_limits<int>::min();
7
8 int curmaxsum()
9 {
10 int sum=0，cursum=-130;
11 for(int i=0; i<n; i++)
12 {
13 sum+=b[i];
14 if(sum<0)
15 sum=b[i];
16 if(sum>cursum)
17 cursum=sum;
18 }
19 return cursum;
20 }
21
22 int maxsub()
23 {
24 for(int i=0; i<n; i++)
25 {
26 memset(b,0,sizeof(b));
27 for(int j=i; j<n; j++)
28 {
29 //printf("\nj=%d\n",j);
30 for(int k=0; k<n; k++)
31 {
32 b[k]+=a[j][k];
33 }
34 /*for(int k=0; k<n-1; k++)
35 printf("%d ",b[k]);
36 printf("%d\n",b[n-1]);*/
37
38 curmaxsum();
39 //printf("cursum=%d\n",cursum);
40 if(cursum>max)
41 max=cursum;
42 // printf("max=%d\n",max);
43 }
44 }
45 return max;
46 }
47
48 int main()
49 {
50 while(scanf("%d",&n)==1)
51 {
52 for(int i=0; i<n; i++)
53 for(int j=0; j<n; j++)
54 scanf("%d",&a[i][j]);
55 // printf("******************************\n\n");
56 maxsub();
57 printf("%d\n",max);
58 }
59 return 0;
60 }
