面试题 17.24. 最大子矩阵 （降维枚举 / 降维动态规划）

LeetCode： 面试题 17.24. 最大子矩阵

枚举起始行和结束行，对列求和，等效成一维最大子序列问题。

降维枚举

class Solution {

    public int[] getMaxMatrix(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        int[] ans = new int[4];
        
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
        	// 记录各列的前缀和
            int[] temp = new int[col];

            for (int j = i; j < row; j++) {
                int cur = 0, tmp = 0;

                for (int k = 0; k < col; k++) {
                    temp[k] += matrix[j][k];
                    if(cur > 0) cur += temp[k];
                    else{
                        cur = temp[k];
                        tmp = k;
                    }

                    if(cur > res){
                        res = cur;
                        ans[0] = i; ans[1] = tmp;
                        ans[2] = j; ans[3] = k;
                    }
                }
            }
        }

        return ans;
    }


}

---

参考： Leetcode 面试题 17.24. 最大子矩阵 (最大子数组和的二维版本）