Submatirix Sum(とゼロのサブマトリックス)

http://www.lintcode.com/en/problem/submatrix-sum/?rand=true Range Sum Query 2 D-Immutableを参照してください。

public class Solution {
    /*
     * @param matrix: an integer matrix
     * @return: the coordinate of the left-up and right-down number
     */
    public int[][] submatrixSum(int[][] matrix) {
        // write your code here
        int[][] res = new int[2][2];
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = matrix[i - 1][j - 1] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int[] start = {i - 1, j - 1};
                for (int k = i; k <= m; k++) {
                    for (int l = j; l <= n; l++) {
                        int[] end = {k - 1, l - 1};
                        if (sum[k][l] - sum[k][j - 1] - sum[i - 1][l] + sum[i - 1][j - 1] == 0) {
                            res[0] = start;
                            res[1] = end;
                            return res;
                        }
                    }
                }
            }
        }
        return res;
    }
}