Difference between revisions of "TADM2E 8.25"

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