(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

We'll proceed along the lines recommended in the chapter by considering the order in which we do the computations and caching the result.

Given an array a(n) of integers we construct a matrix A(n,n) where each row is a lower index and each column is an end index.

Now we note that in each row i and column j the following recursion holds: A[i,j+1] = A[i,j] + a[j+1] for j > i and A[i,j] = a[i] for j = i.

As an example, the first few entries of A(n,n) with a(n) = { -1, 0, 2, ... } would be:

 -1  -1   1 ...
---   0   2 ...
--- ---   2 ...
... ... ... ...


And, the answer returned (minimum length sequence) would be a low and high index of (2,2) and a sum of 2 (with zero based indexing).

Here's python code for the solution:

def max_sum(arr):
'''
arr -- array of integers
return max subsequence sum
>>> max_sum([0,-1,1,3,-1])
(4, (2, 3))
>>> max_sum([-1,-1])
(-1, (-1, -1))
>>> max_sum([-1,-1,3])
(3, (2, 2))
>>> max_sum([1,0,-1,1,1])
(2, (3, 4))
>>> max_sum([-1,1,-1,1,0,1])
(2, (3, 5))
>>> max_sum([0,-1,-2,-1])
(0, (0, 0))
>>> max_sum([-1,0,2])
(2, (2, 2))
'''
n = len(arr)
maxsum, l, h = -1, -1, -1
if n < 1:
return (maxsum, (l,h))
A = [[0 for i in range(n)] for i in range(n)]

for i in range(n):
for j in range(i,n):
A[i][j] = A[i][j-1] + arr[j] if j > i else arr[j]
if A[i][j] > maxsum or (A[i][j] == maxsum and (j-i) < (h-l)):
maxsum = A[i][j]
l, h = i, j
return (maxsum, (l,h))


Another Version (Algorithm from Bentley's programming pearl)

Iterate list. If current int is negative and has absolute value greater than maxSoFar, start over. Otherwise keep rolling.

public class MaxRun {
private int[] array;

private int maxSoFar;//max sum for this very run
private int thisStart;//start position for this very run

private int max;//global max run sum
private int start;//global max run start
private int end;//global max run end

public MaxRun(int[] input) {
array = input;
}

public void run() {
for (int i=0; i<array.length; i++) {
if (array[i]>0 || (-1)*array[i]< maxSoFar) {
maxSoFar += array[i];

if (maxSoFar>max){
max = maxSoFar;
end = i;
start = thisStart;
}
}
else {
maxSoFar = 0;
thisStart = i+1;
}
}

System.out.println("Max sum: " + max + " i: " + start + " j: " + end);
}

public static void main(String args[]) {
MaxRun myRun = new MaxRun(new int[]{1, 0, -2, 5, -3, -1, 6});
myRun.run();
}
}