Posts Maximum Sum Sub-Matrix
Post
Cancel

Maximum Sum Sub-Matrix

Problem Description

Given a 2D matrix, find the maximum possible sum of sub-matrices in that matrix.

Solution

The brute force approach is to get all sub-matrices, calculate the sum and update the max-sum as we go on. Obviously the time complexity will be very high: O(N^2M^2). We can optimize it to O(NM) which is the best possible time complexity possible for any matrix.

  • First create a prefix sum matrix for the given matrix. To do this, first take the row-wise sum. Then do the same thing column wise.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int[][]  pf = new int[n][m];

//Create prefix array

//Row wise
for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
        if(j == 0){
            pf[i][j] = matrix[i][j];
        }else{
            pf[i][j] = pf[i][j-1] + matrix[i][j];
        }

    }
}

//column wise
for(int j=0; j<m; j++){
    for(int i=0; i<n; i++){
    
        if(i == 0){
            pf[i][j] = pf[i][j];
        }else{
            pf[i][j] = pf[i-1][j] + pf[i][j];
        }
    }
}
  • Create a method to get the sum of any given sub-matrix using the above created prefix sum matrix.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int getSumOfSubMatrix(int[][] pf, int topX, int topY, int bottomX, int bottomY){
    int sum = 0;

    if(topX==0 && topY == 0){
        sum = pf[bottomX][bottomY];
    }else if(topY==0){
        sum = pf[bottomX][bottomY]  - pf[topX-1][bottomY];
    }else if(topX == 0){
        sum = pf[bottomX][bottomY] - pf[bottomX][topY-1];
    }else{
        sum = pf[bottomX][bottomY] - pf[bottomX][topY-1] - pf[topX-1][bottomY] + pf[topX-1][topY-1];
    }

    return sum;
}

Now, the important part: We will fix the rows first using two loops. Something like:

snapshot

1
2
3
4
5
6
7
for(int i=0; i<n; i++){ //start row
    for(int j=i; j<n; j++){ //end row
        //logic to get sum of the sub-matrix between startRow and EndRow. 
        //Then use Kadane's algorithm to get the maximum possible column wise.
        //Update the max sum if this is higher
    }
}

Complete Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
package com.gauk;

import java.util.*;

import java.util.*;

class Program {

    public int maximumSumSubmatrix(int[][] matrix) {

        int n = matrix.length;
        int m = matrix[0].length;

        int[][]  pf = new int[n][m];

        //Create prefix array

        //Row wise
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(j == 0){
                    pf[i][j] = matrix[i][j];
                }else{
                    pf[i][j] = pf[i][j-1] + matrix[i][j];
                }

            }
        }

        //column wise
        for(int j=0; j<m; j++){
            for(int i=0; i<n; i++){

                if(i == 0){
                    pf[i][j] = pf[i][j];
                }else{
                    pf[i][j] = pf[i-1][j] + pf[i][j];
                }
            }
        }


        int maxSum = Integer.MIN_VALUE;

        for(int i=0; i<n; i++){ //start row
            for(int j=i; j<n; j++){ //end row

                int[] verticalSumArray = getColumnSumBetweenRows(pf, i, j);
                int sumByKardane = kadanesAlgorithm(verticalSumArray);
                maxSum = Math.max(sumByKardane, maxSum);
            }
        }

        return maxSum;

    }

    public int getSumOfSubMatrix(int[][] pf, int topX, int topY, int bottomX, int bottomY){
        int sum = 0;

        if(topX==0 && topY == 0){
            sum = pf[bottomX][bottomY];
        }else if(topY==0){
            sum = pf[bottomX][bottomY]  - pf[topX-1][bottomY];
        }else if(topX == 0){
            sum = pf[bottomX][bottomY] - pf[bottomX][topY-1];
        }else{
            sum = pf[bottomX][bottomY] - pf[bottomX][topY-1] - pf[topX-1][bottomY] + pf[topX-1][topY-1];
        }

        return sum;
    }

    public int[] getColumnSumBetweenRows(int[][] pf, int startRow, int endRow){

        int columns = pf[0].length;
        int[] vsum = new int[columns];

        for(int i=0; i<columns; i++){
            vsum[i] = getSumOfSubMatrix(pf, startRow, i, endRow, i);
        }

        return vsum;
    }

    public static int kadanesAlgorithm(int[] array) {

        int maxSum = Integer.MIN_VALUE;

        int maxSumTillHere = 0;

        for(int i=0; i<array.length; i++){
            maxSumTillHere = Math.max(maxSumTillHere + array[i], array[i]); //Either the sum will increase if we include the next number OR the next number has a larger value
            maxSum = Math.max(maxSum, maxSumTillHere);
        }

        return maxSum;

    }

}
This post is licensed under CC BY 4.0 by the author.