连续子数组(二维)的最大和

http://www.acmerblog.com/max-sum-rectangle-in-a-matrix-5955.html

二维数组的连续子数组的最大和

二维数组的连续子数组即为一个矩阵，如下图所示

2. 方法二 转化为一维数组计算

这里并不是把整个二维数组转化为一维的，而是说把部分连续的行合并，看成是一行计算。这样枚举所有连续的行，把这些连续的行看成是一个整体，把一列看成是一个数字，问题就转化为上面的一维数组的算法了。还可以采用上面的预处理方法，在O（1）的时间内计算出任意一列的和。代码如下，colSum函数即为预处理函数，我们还可以根据M，N的大小做些优化。算法的复杂度为 O(N * M * min(M,N) ).

01	//求一维数组的最大连续和

02	static int maxSum(int p[][], int startLine,int endLine,int n){

03	int ans = p[endLine][1] - p[startLine-1][1]; //即第一个列(startLine行到endLine行)的和

04	int cmax = ans;

05	for(int i=2; i<=n; i++){

06	int ci = p[endLine][i] - p[startLine-1][i];

07	cmax = Math.max(cmax+ci, ci);

08	ans = Math.max(cmax, ans);

09

}

10	//System.out.println(startLine + " " + endLine + " " +ans);

11	return ans;

12

}

13

14	static int[][] colSum(int arr[][]){

15	int m = arr.length;

16	int n = arr[0].length;

17	int  p[][] = new int[m+1][n+1];

18	for(int i=1; i<=m; i++)

19	for(int j=1; j<=n; j++)

20	p[i][j] = p[i-1][j] + arr[i-1][j-1];

21

return p;

22

}

23

24	static int maxArrSum2(int arr[][]){

25	int m = arr.length;

26	int n = arr[0].length;

27	if(m > n){

28

//对数组进行逆置

29	arr = reverseArr(arr);

30	int tmp = m;

31

m = n;

32

n = tmp;

33

}

34	int p[][] = colSum(arr);

35	int tempMax = Integer.MIN_VALUE;

36

37	//h表示当前矩阵的高度. 即把多少行合并为一行看

38	for(int h=1; h<=m; h++){

39	for(int i=1; i+h-1 <= m; i++){

40	int endLine = i+h-1;

41	//转化为长度为n一维数组，复杂度为O(n)

42	tempMax = Math.max(tempMax, maxSum(p, i, endLine, n));

43

}

44

}

45	return tempMax;

46

}

47

48	static int[][] reverseArr(int arr[][]){

49	int m = arr.length;

50	int n = arr[0].length;

51	int newArr[][] = new int[n][m];

52	for(int i=0; i<m; i++)

53	for(int j=0; j<n; j++)

54	newArr[j][i] = arr[i][j];

55	return newArr;

56

}

方法1：直接计算

我们可以遍历所有的矩形区域，找出其中的最大值，其中遍历的话复杂度为O(M^2 * N^2)，假设二维数组为M行N列。

其中怎么计算子矩阵的和呢？通过预处理，我们可以再O(1)的时间内算出。具体看下面的代码：

arrSum函数即做预处理，得到数组p，p[i][j]表示已Rect(0, 0, i-1, j-1)矩形区域的总和。有了p数组就可以直接计算出任意矩形的总和。

一维数组的连续子数组的最大和

1	static int MaxSum(int arr[], int n){

2	int currentSum = arr[0];

3	int ans = currentSum;

4	for(int i=1; i<n; i++){

5	currentSum = Math.max(currentSum+arr[i], arr[i]);

6	ans = Math.max(ans, currentSum);

7

}

8	return ans;

9

}

 扩展问题

如果二维数组首尾相连，如何计算？

可以先考虑一维数组首位相连的问题。一个方法是把原来的数组进行扩充，例如对于 arr[0 ... n-1 ] 可以看成是  arr[0 ... n-1, 0, 1, ....n-2]。即原数组的长度由原来的n，变为了 2*n-1。实际中计算中没有必要扩充，求余即可。需要注意的是，如果全部都是非负的，我们需要加一个判断，防止计算结果超出数组的总和。

二维数组的计算方法和这个类似。

static int MaxSumLinked(int arr[], int n){

02	int currentSum = arr[0];

03	int ans = currentSum;

04	boolean hasNegative = false;//有可能全部都是非负，这时就没必要往后计算

05	for(int i=1; i<n*2-1; i++){

06	if(i < n && arr[i] < 0) hasNegative = true;

07	currentSum = Math.max(currentSum+arr[i%n], arr[i%n]);

08	ans = Math.max(ans, currentSum);

09	if(i == n-1 && !hasNegative) return ans;

10

}

11	return ans;

12

}

http://blog.csdn.net/linyunzju/article/details/7723730
若二维数组的左右首尾也能相连，像一条首尾相连的带子，算法如下：

1. inline long long MatrixSum(int s, int t, int i, int j)  
2. {  
3.     return PS[i][j]-PS[i][t-1]-PS[s-1][j]+PS[s-1][t-1];  
4. }  
5.   
6. int main()  
7. {  
8.     int m, n, i, j;  
9.     cin >> n >> m;  
10.     for (i=1; i<=n; i++)  
11.         for (j=1; j<=m; j++)  
12.             cin >> A[i][j];  
13.     for (i=0; i<=n; i++)  
14.         PS[i][0] = 0;  
15.     for (j=0; j<=m; j++)  
16.         PS[0][j] = 0;  
17.     // 计算矩阵的部分和  
18.     for (i=1; i<=n; i++)  
19.         for (j=1; j<=m; j++)  
20.             PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1];  
21.     int a, c;  
22.     long long All = A[1][1];  
23.     // 上下边界不会跨过第n行和第1行  
24.     for (a=1; a<=n; a++)  
25.         for (c=a; c<=n; c++)  
26.         {     
27.             // 将子矩阵上下边界设为第a行和第c行  
28.             // 左右边界不会跨过第m列和第1列  
29.             long long Tail = MatrixSum(a, 1, c, 1);  
30.             for (j=2; j<=m; j++)  
31.             {  
32.                 Tail = max(MatrixSum(a, j, c, j),   
33.                     MatrixSum(a, j, c, j)+Tail);   
34.                 All = max(Tail, All);  
35.             }  
36.             // 左右边界会跨过第n列和第1列  
37.             long long Sum = MatrixSum(a, 1, c, 1);  
38.             long long Start = Sum;  
39.             int sind = 1;  
40.             for (i=2; i<=m; i++)  
41.             {  
42.                 Sum += MatrixSum(a, i, c, i);  
43.                 if (Sum > Start) {Start = Sum; sind = i;}  
44.             }  
45.             Tail = MatrixSum(a, m, c, m);  
46.             int tind = m;  
47.             for (j=m-1; j>=1; j--)  
48.             {  
49.                 Sum += MatrixSum(a, j, c, j);  
50.                 if (Sum > Tail) {Tail = Sum; tind = j;}  
51.             }  
52.             if (sind<tind && Start+Tail>All)  
53.                 All = Start+Tail;  
54.         }  
55.     cout << All;  
56. }  

2. 求三维数组（长方体）的子方体之和的最大值。

2. 解法：

思路和二维一样，但时间复杂度增加到O(n^5)。通过将高维转化为低维的方法，每增加一维时间复杂度要增加O(n^2)。
方体的部分和计算公式如下：PS[i][j][k] = A[i][j][k]+PS[i-1][j][k]+PS[i][j-1][k]+PS[i][j][k-1]-PS[i-1][j-1][k]-PS[i-1][j][k-1]-PS[i][j-1][k-1]+PS[i-1][j-1][k-1];

1. int A[MAXN][MAXN][MAXN];  
2. int PS[MAXN][MAXN][MAXN];  
3.   
4. inline int CubeSum(int a, int b, int c, int d, int i, int j)  
5. {  
6.     return PS[b][d][j]-PS[a-1][d][j]-PS[b][c-1][j]-PS[b][d][i-1]+  
7.         PS[a-1][c-1][j]+PS[a-1][d][i-1]+PS[b][c-1][i-1]-PS[a-1][c-1][i-1];  
8. }  
9.   
10. int main()  
11. {  
12.     int n, m, h, i, j, k;  
13.     cin >> n >> m >> h;  
14.     for (i=1; i<=n; i++)  
15.         for (j=1; j<=m; j++)  
16.             for (k=1; k<=h; k++)  
17.                 cin >> A[i][j][k];  
18.     for (i=0; i<=n; i++)  
19.         for (j=0; j<=m; j++)  
20.             PS[i][j][0] = 0;  
21.     for (i=0; i<=n; i++)  
22.         for (k=0; k<=h; k++)  
23.             PS[i][0][k] = 0;  
24.     for (j=0; j<=m ; j++)  
25.         for (k=0; k<=h; k++)  
26.             PS[0][j][k] = 0;  
27.     // 计算长方体的部分和  
28.     for (i=1; i<=n; i++)  
29.     for (j=1; j<=m; j++)  
30.     for (k=1; k<=h; k++)  
31.         PS[i][j][k] = A[i][j][k]+PS[i-1][j][k]+PS[i][j-1][k]+PS[i][j][k-1]-  
32.             PS[i-1][j-1][k]-PS[i-1][j][k-1]-PS[i][j-1][k-1]+PS[i-1][j-1][k-1];  
33.     int a, b, c, d;  
34.     int All = A[1][1][1];  
35.     // 限制第一维的取值范围  
36.     for (a=1; a<=n; a++)  
37.     for (b=a; b<=n; b++)  
38.         // 限制第二维的取值范围  
39.         for (c=1; c<=m; c++)  
40.         for (d=c; d<=m; d++)  
41.         {  
42.             // 只剩下最后一维没有确定，利用一维部分和的方法  
43.             int Tail = CubeSum(a,b,c,d,1,1);  
44.             for (j=2; j<=k; j++)  
45.             {  
46.                 int cur = CubeSum(a,b,c,d,j,j);  
47.                 Tail = max(Tail+cur, cur);  
48.                 All = max(Tail, All);  
49.             }  
50.         }  
51.     cout << All;  
52. }

http://www.cnblogs.com/huiyuan/p/liantong.html

二维数组连续的二维子数组的和（左右相连，上下也相连）

分析思路：这个最大子矩阵和就是把平面上下相连和左右相连，无论先连哪一边都一样。先随便找一条横边和一条竖边即可，然后原问题等价于把4个这样的平面拼在一起，然后找不超过一个平面大小的最大子矩阵。先转换为1维的问题，枚举上下边界，用一维的方法用单调队列求解。

-- TODO