2

我试图从二维矩阵中找出大小为 k 的最大和子矩阵。

我已经正确实现了一切，但我仍然得到：

索引超出范围 -1 异常

我对这件事的想法如下：

  1. 将原始矩阵预处理为，pre_processes[][]以便我可以在恒定时间内找到 sm 。

  2. 如果其中任何一个 row-k 或 col-k 大于 0，则从行和列的索引 k-1 开始，如果两者都更大，则从当前总和中减去该值，加上它们的联合，这将是pre_processes[row-1][column-1]

代码：

public int max_sum(int[][] image,int k ){
    int[][] pre_processed = new int[image.length][image[0].length];
    pre_processed[0][0] = image[0][0];
    for (int row = 1;row < image.length-k+1;row++){
        pre_processed[row][0] += image[row][0] + pre_processed[row-1][0];
    }

    for (int column = 1;column < image.length-k+1;column++){
        pre_processed[0][column] += image[0][column] + pre_processed[0][column-1];
    }

    for (int rows = 1;rows < image.length;rows++){
        for (int columns = 1;columns < image[0].length;columns++){
            pre_processed[rows][columns] = pre_processed[rows-1][columns]+pre_processed[rows][columns-1]+
                                           image[rows][columns]-pre_processed[rows-1][columns];
        }
    }

    int total,brightness = Integer.MIN_VALUE;

    for (int row_2 = k-1;row_2 < image.length;row_2++){
        for (int col_2 = k-1;col_2 < image[0].length;col_2++){

            total = pre_processed[row_2][col_2];
            if (row_2-k > 0)
                total -= pre_processed[row_2-k][col_2];
            if (col_2-k > 0)
                total -= pre_processed[row_2][col_2-k];
            if (row_2-k > 0 && col_2-k > 0)
                total += pre_processed[row_2-1][col_2-1];
            if (total > brightness)
                brightness = total;
        }
    }

    return brightness;
}

public static void main(String[] args){
    int[][] image = {
        {2 ,  3,   4, 10, 12},
        {20 , 30, 14, 11, 13},
        {29 , 39, 40, 12, 24},
        {40 , 39, 39, 15, 35},
        {100 ,23, 24, 60, 80}
    };
}
4

0 回答 0