# 编程之美-子数组的最大和（二维）

```package beautyOfCoding;

import java.util.Arrays;
import java.util.Random;

public class MaxSubArraySum2 {

/**
* 编程之美 子数组之和的最大值（二维）
*/
private static final int ROW = 5;
private static final int COL = 6;
private static final int MAX = 127;
private boolean invalidInput = false;
private static int[] source;	//[-127,127]共127*2+1个数
static {
int n = MAX * 2 + 1;
source = new int[n];
for (int i = 0; i < n; i++) {
source[i] = i - MAX;
}
}

public static void main(String[] args) {
//生成指定行数和列数的数组。数组元素是[-127,127]范围内的随机数
int[][] B = new int[ROW][COL];
int n = MAX * 2 + 1;
Random random = new Random();
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
int pos = random.nextInt(n);
int num = source[pos];
B[i][j] =  num;
}
System.out.println(Arrays.toString(B[i]));
}

/*int[][] B = {
{0, -2, -7, 0},
{9, 2, -6, 2},
{-4, 1, -4, 1},
{-1, 8, 0, -2}
};*/

//方法A-全枚举
MaxSubArraySum2 test = new MaxSubArraySum2();
int max = test.maxSubArraySumA(B);
if (test.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max);
}
//方法B-部分和
MaxSubArraySum2 test2 = new MaxSubArraySum2();
int max2 = test2.maxSubArraySumB(B);
if (test2.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max2);
}
//方法C-转化为一维
MaxSubArraySum2 test3 = new MaxSubArraySum2();
int max3 = test3.maxSubArraySumB(B);
if (test3.invalidInput) {
System.out.println("invalid input");
} else {
System.out.println(max3);
}
}

/**
* 转化为一维。
*/
public int maxSubArraySumC(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
for (int a = 0; a < row; a++) {
for (int c = a; c < row; c++) {
int[] BC = this.getBC(B, a, c);
int oneDimension = this.maxInOneDimensionalArray(BC);
if (max < oneDimension) {
max = oneDimension;
}
}
}
}
return max;
}

/**
* maxSubArraySumC的辅助方法。得到第a行到第c行所代表的一维数组
*/
public int[] getBC(int[][] B,int a,int c){
int col=B[0].length;
int[] BC = new int[col];
for(int i=0;i<col;i++){
for(int j=a;j<=c;j++){
BC[i] += B[j][i];
}
}
return BC;
}

//子数组之和的最大值-一维
public int maxInOneDimensionalArray(int[] a){
//略去参数检查
int Start=0;
int All=0;
for(int i=0,len=a.length;i<len;i++){
All=this.maxNum(a[i],Start+a[i],All);
Start=this.maxNum(a[i],a[i]+Start);     //if start<0, start=a[i]
}
return All;
}

/**
* 用部分和的形式。其中辅助数组PS额外多一行多一列（默认初始化为0），方便计算“部分和”的“部分和”，需仔细体会
* PS[i][j] 表示元素(1,1)(对应原始数组B的B[0][0])和当前元素(i,j)为顶点对的子矩阵的部分和，部分和的计算如下：
* PS[i][j] = A[i][j]+PS[i-1][j]+PS[i][j-1]-PS[i-1][j-1]
*/
public int maxSubArraySumB(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
int col = B[0].length;
int[][] PS = new int[row+1][col+1];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
PS[i+1][j+1] = PS[i][j+1] + PS[i+1][j ] - PS[i][j] + B[i][j];
}
}
max = this.maxPSij(PS);
}
return max;
}

/**
* maxSubArraySumB的辅助方法
* 求“部分和”的“部分和”：求得(imin, imax, jmin, jmax)代表的矩形区域的和，即题目所求
*/
public int maxPSij(int[][] PS) {
int max = Integer.MIN_VALUE;
int row = PS.length;
int col = PS[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
for (int m = i; m < row; m++) {
for (int n = j; n < col; n++) {
max = this.maxNum(max, PS[i][j], PS[m][n],
(PS[m][n] - PS[m][j] - PS[i][n] + PS[i][j]));
}
}
}
}
return max;

}

/**
* 穷举法，求部分和也是用枚举，有六个for循环，复杂度相当高，不过可用于检验其他方法是否正确
*/
public int maxSubArraySumA(int[][] B) {
int max = Integer.MIN_VALUE;
if (B == null) {
invalidInput = true;
} else {
int row = B.length;
int col = B[0].length;
for (int imin = 0; imin < row; imin++) {
for (int imax = imin; imax < row; imax++) {
for (int jmin = 0; jmin < col; jmin++) {
for (int jmax = jmin; jmax < col; jmax++) {
int tmpSum = sum(B, imin, imax, jmin, jmax);
if (tmpSum > max) {
max = tmpSum;
}
}
}
}
}
}
return max;
}

/**
* maxSubArraySumA的辅助方法
* 枚举求得(imin, imax, jmin, jmax)代表的矩形区域的和
*/
public int sum(int[][] B, int imin, int imax, int jmin, int jmax) {
int result = 0;
for (int i = imin; i <= imax; i++) {
for (int j = jmin; j <= jmax; j++) {
result += B[i][j];
}
}
return result;
}

/**
* 返回最大的数
*/
public int maxNum(int x, int... yy) {
for (int y : yy) {
if (x < y) {
x = y;
}
}
return x;
}

}
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊