Given an array ofn * mmatrix, and a moving matrix window (sizek * k), move the window from top left to botton right at each iteration, find the maximum sum inside the window at each moving.
Return0if the answer does not exist.

Have you met this question in a real interview?

Yes

Example

For matrix

[
  [1, 5, 3],
  [3, 2, 1],
  [4, 1, 9],
]

The moving window size k =2.
return 13.

At first the window is at the start of the array like this

[
  [|1, 5|, 3],
  [|3, 2|, 1],
  [4, 1, 9],
]

,get the sum11;
then the window move one step forward.

[
  [1, |5, 3|],
  [3, |2, 1|],
  [4, 1, 9],
]

,get the sum11;
then the window move one step forward again.

[
  [1, 5, 3],
  [|3, 2|, 1],
  [|4, 1|, 9],
]

,get the sum10;
then the window move one step forward again.

[
  [1, 5, 3],
  [3, |2, 1|],
  [4, |1, 9|],
]

,get the sum13;
SO finally, get the maximum from all the sum which is13.

1. 沿用一维数组中求子数组和时的前sum预处理，我们可以对矩阵中的子矩阵预处理sum[i][j]为以i,j为右下角的子矩阵的和。这样可以O(1)计算任一子矩阵的和
2. 扫描矩阵直至i + k 和 j + k到达 矩阵右下角

1，2，3，4

5，6，7，8

9，10，11，12

如果想求 7，8，11，12这个子数组，只需要用sum[3][3] - sum[0][3] - sum[3][1] + sum[0][1] 因为sum[0][1]被减了两次

public class Solution {
    /*
     * @param matrix: an integer array of n * m matrix
     * @param k: An integer
     * @return: the maximum number
     */
    public int maxSlidingMatrix(int[][] matrix, int k) {
        // write your code here
        if (k == 0 || matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0 || k > matrix.length || k > matrix[0].length) {
            return 0;
        }

        int[][] sum = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                sum[i][j] = matrix[i][j];
                if (i > 0 && j > 0) {
                    sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
                } else if (i > 0) {
                    sum[i][j] += sum[i - 1][j];
                } else if (j > 0) {
                    sum[i][j] += sum[i][j - 1];
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i + k <= matrix.length; i++) {
            for (int j = 0; j + k <= matrix[0].length; j++) {
                int curSum = sum[i + k - 1][j + k - 1];
                //System.out.print(curSum + ",");
                if (i > 0 && j > 0) {
                    curSum -= sum[i + k - 1][j - 1] + sum[i - 1][j + k - 1] - sum[i - 1][j - 1];
                } else if (i > 0) {
                    curSum -= sum[i - 1][j + k - 1];
                } else if (j > 0) {
                    curSum -= sum[i + k - 1][j - 1];
                }

                max = Math.max(max, curSum);
            }
            //System.out.println("");
        }
        return max;
    }
}