算法题解-面试题 17.24. 最大子矩阵

1.题目描述

给定一个正整数和负整数组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。

返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。

注意：本题相对书上原题稍作改动

示例:

输入:
[
   [-1,0],
   [0,-1]
]
输出: [0,1,0,1]
解释: 输入中标粗的元素即为输出所表示的矩阵

说明：

1 <= matrix.length, matrix[0].length <= 200

2.代码实现

class Solution {
    public static int[] getMaxMatrix(int[][] matrix) {
        //矩阵的行数
        int row = matrix.length;
        //矩阵的列数
        int col = matrix[0].length;

        //最值
        int answerMax = Integer.MIN_VALUE;

        //位置数组
        int[] answerArray = new int[4];

        //列上的前缀合
        int[][] colPrefix = new int[row][col];
        for (int i = 0; i < col; i++) {
            //第一行各项的前缀合
            colPrefix[0][i] = matrix[0][i];

            //第二行之后的各项前缀合
            for (int j = 1; j < row; j++) {
                colPrefix[j][i] = colPrefix[j-1][i] + matrix[j][i];
            }
        }

        //临时数组，用来保存接下来转化的一维数组
        int[] temp = new int[col];

        //依次枚举每一种转化的情况
        for (int fromRow = 0; fromRow < row; fromRow++) {
            for (int toRow = fromRow; toRow < row; toRow++) {
                //fromRow到toRow进行合并
                for (int i = 0; i < col; i++) {
                    temp[i] = fromRow == 0 ? colPrefix[toRow][i] : colPrefix[toRow][i] - colPrefix[fromRow-1][i];
                }

                //求解每一种情况的最大子数组和
                int[] maxArrayResult = getMaxArray(temp);

                //刷新最大的情况
                int max = maxArrayResult[0];
                int maxFromCol = maxArrayResult[1];
                int maxToCol = maxArrayResult[2];
                if (max > answerMax){
                    answerMax = max;

                    answerArray[0] = fromRow;
                    answerArray[1] = maxFromCol;
                    answerArray[2] = toRow;
                    answerArray[3] = maxToCol;
                }
            }
        }

        return answerArray;
    }

    /**
     * 求解一维数组的最大子数组和
     * @param nums
     * @return
     */
    private static int[] getMaxArray(int[] nums) {
        //上一个以当前节点为终结节点的最大子数组和
        int preMax = nums[0];

        //当前的以当前节点为终结节点的最大子数组和
        int max = nums[0];

        //真正的起止列数
        int realFromCol = 0;
        int realToCol = 0;

        //临时的开始列数
        int fromCol = 0;

        //枚举
        for (int i = 1; i < nums.length; i++) {
            if (preMax <= 0){
                preMax = nums[i];

                //如果需要刷新最大值和起止列
                if (preMax > max){
                    max = preMax;

                    realFromCol = i;
                    realToCol = i;
                }

                //起始列发生了变化
                fromCol = i;
            }else {
                preMax = preMax + nums[i];

                //如果需要刷新最大值
                if (preMax > max){
                    max = preMax;

                    realFromCol = fromCol;
                    realToCol = i;
                }
            }
        }

        return new int[]{max, realFromCol, realToCol};
    }
}