Max Sum Subarray Problem: Matrix

Problem 1

Given a MxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum.

Idea

Let OPT(i,j) be the maximum sum of the matrix starting at row i and ending at row j. For each (i, j) we can reduce the sub-matrix to an array by summing each column from i to j and use the Kadane's algorithm of max sum subarray problem.

Algorithm

Comparing OPT(i,j) of all (i, j) pairs to find out the largest sub-matrix. The sum of elements of column k from row i to row j can be obtained in constant time by building incrementally on the fly.

Rendered by QuickLaTeX.com

Complexity

O(m^{2}n) in time complexity and O(n) in space.

Implementation

Problem 2

Given a binary matrix, find out the maximum size sub-matrix with all 1s/0s.

Solution 1: (convert to Max Sum Subarray Problem)

Idea

Similar to max sum submatrix problem, only have a different way to computer sum of each column in (i, j). Take one-cluster for example: if all elements of the column from row i to row j are 1, the sum is 1, otherwise, it is the negative infinite, which basically disqualifies this column in the max submaxtrix from (i,j).

Complexity:

Same to problem 1. O(m^{2}n) in time complexity and O(n) in space.

Solution 2: (convert to Maximum Area in Histogram Problem)

Idea

Solution 1 is redundant because not all pairs of rows needs to be checked. For a column, only continuous 1s can form a sub-matrix. all continuous 1s in a column can be found in linear time. Take each continuous 1s bar in a column as a bar in a histogram. The histogram covers all n columns and its bars are all aligned on a certain row.

Algorithm

Need to process each row (each histogram baseline) from bottom up. Let OPT(i) be the maximum 1-cluster starting from row 1 and ending exactly at row i. The sub-problem can be solved by taking continuous 1-elements in each column starting from i up as a bar in a histogram. OPT(i) is then converted to finding the maximum rectangular in the histogram. As we move up one row after another, the histogram in OPT(i) is used to build OPT(i-1): if a(i,j) is 1, then bar(i-1) = bar(i) -1, if a(i,j) is 0, a new bar of the histogram should be built from a(i-1,j). Because each of m elements in each column is only checked once, building each bar(i) is amortized in constant time.

Complexity

There are m histograms, and constructing each histogram is O(n). Linear time algorithm exists for computing the largest rectangle in a histogram. Thus, the total complexity is O(mn).

Implementation

 

 
 
 
Digiprove sealCopyright secured by Digiprove © 2013 Del Bao

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">