# 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.

### Complexity

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

# Problem 2

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

### 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.

### 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).