Tuesday, January 15, 2019

Maximum sum subarray solution using Kadane's Algorithm

Maximum sum subarray problem :

Given a matrix of n rows and n coloums , consisting of integers , find the submatrix with maximum sum among all submatrices.

Online Judge Codechef link : https://www.codechef.com/problems/MXSUBMT

Quick video tutorial : https://www.youtube.com/watch?v=yCQN096CwWM

Explanation :

How to extend 1D kadane to this problem?

Consider a 2D array:

1 3
4 -1
2 4
5 6

Our requirement is to find max sum rectangle in this matrix. So either both of the elements of each column occur together or they don't.

To use Kadane in this problem create a new array with sum at each row equal to sum of the elements of each row in this matrix. Finding the max sum array in this 1D array is equal to a 2D array in this matrix.

For more number of columns in the matrix, we loop :

i=0, i<cols, ++i
    j=i, j<cols, ++j
        calc this sum 1D array using rows from i to j
        apply kadane to this squashed array to find corresponding 2D max sum matrix in rows from i to j
        check to see if this is max sum sub matrix overall

Max sum submatrix may or may not start at a particular i so we need to loop i upto number of cols with j from i to no of cols.

Implementation for codechef problem link:



No comments:

Post a Comment