## Sunday, November 9, 2014

### UVa Problem 108 - Maximum Sum

Problem:

Solution:

The problem is easy to solve with brute force, except that would be slow. The key idea is, if we search for the maximum rectangle, it already takes $100^4$ tries to find out which sub rectangle is the maximum, we don't want each try requires a lot of time to compute the sum of that rectangle.

Fortunately, with some pre-processing, it is possible to make the computation of the sum of that sub-rectangle $O(1)$. The key idea is about running sum.

Let's look at a 1 dimensional problem first. Suppose we want to pre-process this array to make computation of any range sum fast:

[1, 2, -3, 0, 4, 7, 6]

To do so, we can first compute the running sums (the sum of the values up to index)

[1, 3, 0, 0, 4, 11, 17]

Then all we need to do is to read from the running sum and subtracts.

For example, if we want the sum from -3 to 7 (i.e. index 2 to index 5), we know the sum from 1 to 2 (i.e index 0 to index 1) is 3, and the sum from 1 to 7 (e.g. index 0 to index 5) is 11. So the running sum from -3 to 7 (i.e. again, index 2 to index 5) is just 11 - 3 = 8.

To abstract this a little, the running sum from index a to index b (inclusive) is the running sum from index 0 to index b - running sum from index 0 to index a - 1.

One tiny technical nuisance, a - 1 might be -1, and we need to handle this in the code. To avoid having to do so, we simply prefix the original array by a 0, that does not impact the sum, and all new indexes >= 1, that make -1 a legal operation to do!

How do we extend this idea to 2 dimensional arrays? Same! Except we have a slightly more complicated formula.

The key idea about subtraction is that we wanted to compute the right set. In 2D, the right set need to be computed differently. Suppose we wanted the sum from (a, b) to (c, d), the diagram look like this where S has coordinate (a, b) and E has coordinate (c, d).

X X X X X X
X X S X X X
X X X X X X
X X X X X E

To compute the rectangle from S to E, we assume the sum from (0, 0) to any point is available. We start with the sum (0, 0) to E, which includes all values like this.

X X X X X X
X X S X X X
X X X X X X
X X X X X E

Then we subtract away the left hand side (0, 0) to (a - 1, d), that gives

X X X X X X
X X S X X X
X X X X X X
X X X X X E

We need to subtract more, the top, but the best we could do is (0, 0) to (c, b - 1), so we end up with

X X X X X X
X X S X X X
X X X X X X
X X X X X E

With the red part subtracted twice, but that's fine, we just add them (0, 0) to (a - 1, b - 1)

That concludes the $O(1)$ algorithm for computing the sub-rectangle sum, it remains how those values are pre-computed. In fact, they use the same technique. The sum of a bigger rectangle is the sum of the two previous rectangle minus the diagonal one overlapped. The pre-computation take $O(n^2)$ time.

Last but not least, the book mention there is an $O(n^3)$ algorithm. I also happen to know there is an $O(n)$ algorithm for computing the maximum contiguous sum in 1 dimension. So maybe I can spend more time later to try to derive the $O(n^3)$ algorithm myself :)

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=44

#include "UVa108.h"

#include <iostream>
#include <vector>

using namespace std;

int UVa108()
{
int n;
cin >> n;
vector<vector<int> > input;
input.resize(n);
for (int row = 0; row < n; row++)
{
input[row].resize(n);
for (int col = 0; col < n; col++)
{
cin >> input[row][col];
}
}

// running_sum[i][j] = sum[0 .. (i - 1)][0 .. (j - 1)]
// so running_sum[0][*] = running_sum[*][0] = 0
vector<vector<int> > running_sum;
running_sum.resize(n + 1);
for (int row = 0; row < n + 1; row++)
{
running_sum[row].resize(n + 1);
for (int col = 0; col < n + 1; col++)
{
if (row == 0 || col == 0)
{
running_sum[row][col] = 0;
}
else
{
// x x x x
// x x D C
// x x B A
running_sum[row][col] = running_sum[row - 1][col] + running_sum[row][col - 1] - running_sum[row - 1][col - 1] + input[row - 1][col - 1];
}
}
}

bool first = true;
int max_sum = 0;

// 100 ^ 4 cases
for (int sr = 0; sr < n; sr++)
{
for (int sc = 0; sc < n; sc++)
{
for (int er = sr; er < n; er++)
{
for (int ec = sc; ec < n; ec++)
{
// x x x x x
// x x D x C
// x x x x x
// x x B x A
int sum = running_sum[er + 1][ec + 1] - running_sum[sr][ec + 1] - running_sum[er + 1][sc] + running_sum[sr][sc];
if (first)
{
max_sum = sum;
first = false;
}
else
{
max_sum = max(sum, max_sum);
}
}
}
}
}
cout << max_sum << endl;

return 0;
}