Difference between revisions of "TADM2E 8.25"
(Recovering wiki) 
(No difference)

Revision as of 18:24, 11 September 2014
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][j1] + arr[j] if j > i else arr[j] if A[i][j] > maxsum or (A[i][j] == maxsum and (ji) < (hl)): 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(); } }