Getting wrong sub-matrix from a matrix with an error of -1

42 Views Asked by At

I am trying to find out the maximum sum sub matrix of size k from a 2d matrix.

I have implemented everything correctly, but still I'm getting:

index out of bounds -1 exception

The idea I'm following for this thing as follows:

  1. Preprocess the the original matrix into pre_processes[][] so that I can find sm in constant time.

  2. Start from index k-1 fro both row and column if any of them row-k or col-k is greater than 0 subtract that from the current sum if both are greater add their union which will be at pre_processes[row-1][column-1]

Code:

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}
    };
}
0

There are 0 best solutions below