# TADM2E 8.25

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(); } }