Class Code06_MaxSubMatrixSum

src/videocode/Code06_MaxSubMatrixSum.java:3–160

package videocode;

public class Code06_MaxSubMatrixSum {

	// 非常好想
	// 面试这么写一定没分的方法
	public static int maxSubMatrixSum1(int[][] m) {
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
			return 0;
		}
		int M = m.length;
		int N = m[0].length;
		int ans = Integer.MIN_VALUE;
		for (int lur = 0; lur < M; lur++) {
			for (int luc = 0; luc < N; luc++) {
				// (lur, luc)
				for (int rdr = lur; rdr < M; rdr++) {
					for (int rdc = luc; rdc < N; rdc++) {
						// (rdr, rdc)
						int sum = 0;
						for (int i = lur; i <= rdr; i++) {
							for (int j = luc; j <= rdc; j++) {
								sum += m[i][j];
							}
						}
						ans = Math.max(ans, sum);
					}
				}
			}
		}
		return ans;
	}

	public static int maxSubMatrixSum2(int[][] m) {
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
			return 0;
		}
		int M = m.length;
		int N = m[0].length;
		int ans = Integer.MIN_VALUE;
		for (int start = 0; start < M; start++) { 
			int[] arr = new int[N]; // 0 ,0,0,0,..
			for (int cur = start; cur < M; cur++) {		
				for (int i = 0; i < N; i++) {
					arr[i] += m[cur][i];
				}
				ans = Math.max(ans, maxSubArraySum(arr));
			}
		}
		return ans;
	}

	public static int maxSubMatrixSum3(int[][] m) {
		if (m == null || m.length == 0 || m[0] == null || m[0].length == 0) {
			return 0;
		}
		m = m.length < m[0].length ? m : rotate(m);
		int M = m.length;
		int N = m[0].length;
		int ans = Integer.MIN_VALUE;