Tuesday, February 23, 2010

UVa 108

This is a well known problem. Also called Kadane's 2D problem, it asks to find the maximum sub matrix from a given matrix of integers. The theory is to reduce it to Kadane's 1D problem which aims at finding the maximum sub array in a given array of integers. How do we reduce, this is how:

1) First find the column sums, can be done on the fly. O(n^2)
2) Then just chose pair of rows from this table of column sums. O(n^2)
3) For each pair selected find the partial sum of each column from 1 to n
4) Run Kadane's 1D on the 1D array found above. O(n)
5) Voila sub matrix found in O(n^3)

Here it goes:
using namespace std;
int tab[101][101];
int main() {
int n;
while(scanf("%d",&n)==1) {
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
int mx=tab[1][1];
for(int i=0;i<n;++i) {
for(int j=i+1;j<=n;++j) {
int temp=0;
for(int k=1;k<=n;++k) {
if(temp<0) temp=0;
return 0;

1 comment:

  1. There is a problem about your solution: for this problem, you can't have a empty rectangle, so the maximum must be negative if all the numbers are negative. For example, your code will output 0 for this test: 2 -1 -1 -1 -1, and the true answer is -1.