OpenJudge 1768: Kadane's Algorithm on 2D Arrays

OpenJudge 1768: Kadane's Algorithm on 2-D Arrays

Simple Version

Given a 2-D matrix of integers, find the sub-matrix of this whose sum is maximized, and find that sum. The size of the matrix is no larger than 100 by 100.

Analysis

O(N^4) - Works, but naive

    That's true, an naive O(N^4) version would work. We simply need to calculate (two dimensional!) prefix sums first.

A quick review to what 2-D prefix sums are:

    The 2-D prefix sum of two coordinates, X and Y, is the sum of all elements that have X-coordinate less than or equal to X, and Y coordinate less than or equal to Y.

    It can be calculated through tabulation by removing overlapping areas.

    Let P be the prefix sum array and V be the array of values, so the formula is as follows:

    P[x, y] = V[x, y] - P[x-1, y] - P[x, y-1] + P[x-1, y-1].

    We need to add the P[x-1, y-1] at the end since subtracting P[x-1, y] and P[x, y-1] we had overlapped the P[x-1, y-1].

Then, all we need to do is select two points - one representing the upper left-hand corner of the sub-matrix and one representing the lower right-hand corner.

Selecting the two points runs in O(N^4).

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

int aray[105][105], psum[105][105];
int comp[105];

int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int N; cin >> N;
 for(int i=0; i<N; i++) for(int j=0; j<N; j++)
 {
  cin >> aray[i][j];
  //psum[i][j] = aray[i][j] + (j == 0) ? 0 : psum[i][j-1]; // prefix sum optimization
 }
 int cbest = -256;
 for(int sy=0; sy<N; sy++) for(int se=sy; se<N; se++)
 {
  memset(comp, 0, sizeof comp);
  for(int i=0; i<N; i++) for(int j=sy; j<=se; j++) comp[i] += aray[i][j];
  int cmax = comp[0];
  int best = comp[0];
  for(int i=0; i<N; i++)
  {
   cmax = max(comp[i], cmax+comp[i]);
   best = max(best, cmax);
  }
  cbest = max(cbest, best);
 }
 cout << cbest << endl;
}

O(N^3) - Now we're talking!

But we can still easily do better.

First of all, we don't need to do a 2-D prefix sum, we can just do a collection of 1-D prefix sums.

Second of all, we can select an interval of the collections in O(N^2).

Third of all, Kadane's algorithm can run in O(N).

Multiplying the selection and dynamic programming together, we get an O(N^3) approach.

To elaborate, we don't use the same method as O(N^4) to calculate prefix sums. We calculate the sum of every element in that element's column.

Example:

Given an array

5 -1 2 6

1 10 0 1

0 -9 8 1

We don't sum it by row AND by column, as in the O(N^4) method, like this:

5 4  6  12

6 15 17 24

6 6  16 24

We sum it by rows:

5 -1 2 6

6 9  2 7

6 0 10 8

Then, we go through a process of "selecting" a upper line and a lower line:

5 -1 2 6

--------- HIGH

1 10 0 1

0 -9 8 1

--------- LOW

After we have this, we calculate the sum of the elements in between - but not like this, with the prefix sums we just calculated. This allows for the O(N) optimization.

Kadane's algorithm can run in O(N), as a matter of fact. Here's the pseudocode for Kadane's algorithm:

CBEST = V[0], CMAX = V[0]

FOR EL from 1 to N-1 INCLUSIVE do:

    CMAX = maximum of V[EL] and CMAX + V[EL]

    CBEST = maximum of CBEST and CMAX

answer: CBEST

We implement this in our inner loop to obtain an O(N^3) algorithm.

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;

int aray[105][105], psum[105][105];
int comp[105];

int main()
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int N; cin >> N;
 for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)
 {
  cin >> aray[i][j];
  psum[i][j] = aray[i][j] + psum[i][j-1]; // prefix sum optimization
 }
 int cbest = -512;
 for(int sy=1; sy<=N; sy++) for(int se=sy; se<=N; se++)
 {
  memset(comp, 0, sizeof comp);
  for(int i=1; i<=N; i++) comp[i] = psum[i][se] - psum[i][sy-1];
  int cmax = comp[0], best = comp[0];
  for(int i=1; i<=N; i++)
  {
   cmax = max(comp[i], cmax+comp[i]);
   best = max(best, cmax);
  }
  cbest = max(cbest, best);
 }
 cout << cbest << endl;
}