Difference between revisions of "TADM2E 8.25"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Correct solution for the problem as per the question instructions)
Line 1: Line 1:
−
We'll proceed along the lines recommended in the chapter by considering the order in which we do the computations and caching the result.
+
This is just a special case of the maximum contiguous sum problem. Instead of computing the result for 0,n instead we compute for i,j. We use the same logic, but as per the question we return 3 values indicating the index positions i', j', and max for the maximum sum of the i'th through j'th numbers.  Note that this solution has a worst case running time of O(n), and requires constant additional space. Also note that this solution does not appear, to me, to really be a 'dynamic programming' algorithm.
  
−
Given an array <code>a(n)</code> of integers we construct a matrix <code>A(n,n)</code> where each row is a lower index and each column is an end index.
+
public class Solution {
  
−
Now we note that in each row <code>i</code> and column <code>j</code> the following recursion holds: <code>A[i,j+1] = A[i,j] + a[j+1] for j > i</code> and <code>A[i,j] = a[i] for j = i</code>.
+
public static int[] maxsum(int i, int j, int[] a) {
 +
int max = Integer.MIN_VALUE;
 +
int cur_max = Integer.MIN_VALUE;
 +
 +
int cm_i = i;
 +
int cm_j = i;
 +
int m_i = i;
 +
int m_j = i;
  
−
As an example, the first few entries of <code>A(n,n)</code> with <code>a(n) = { -1, 0, 2, ... }</code> would be:
+
for (; i <= j; i++) {
 +
int x = a[i];
 +
 +
if(cur_max + x > x){
 +
cur_max += x;
 +
cm_j++;
 +
}else{
 +
cur_max = x;
 +
cm_i = cm_j = i;
 +
}
 +
 +
if(cur_max > max){
 +
m_i = cm_i;
 +
m_j = cm_j;
 +
 +
max = cur_max;
 +
}
  
−
<pre>
+
}
−
-1  -1  1 ...
 
−
---  0  2 ...
 
−
--- ---  2 ...
 
−
... ... ... ...
 
−
</pre>
 
  
−
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).
+
return new int[] {m_i, m_j, max};
 +
}
  
−
Here's python code for the solution:
+
public static void main(String[] args) {
 +
int[] a = new int[]{31, -41, 59, 26, -53, 58, 97, -93, -23, 84};
 +
int[] ijmax = maxsum(5, a.length -1, a);
 +
System.out.printf("i=%d, j=%d, sum=%d\n", ijmax[0], ijmax[1], ijmax[2]);
 +
}
  
−
<pre>
+
}
−
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))
 
−
</pre>
 
−
 
 
−
'''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();
 
−
    }
 
−
}
 

Revision as of 15:25, 22 October 2014

This is just a special case of the maximum contiguous sum problem. Instead of computing the result for 0,n instead we compute for i,j. We use the same logic, but as per the question we return 3 values indicating the index positions i', j', and max for the maximum sum of the i'th through j'th numbers. Note that this solution has a worst case running time of O(n), and requires constant additional space. Also note that this solution does not appear, to me, to really be a 'dynamic programming' algorithm.

public class Solution {

public static int[] maxsum(int i, int j, int[] a) { int max = Integer.MIN_VALUE; int cur_max = Integer.MIN_VALUE;

int cm_i = i; int cm_j = i; int m_i = i; int m_j = i;

for (; i <= j; i++) { int x = a[i];

if(cur_max + x > x){ cur_max += x; cm_j++; }else{ cur_max = x; cm_i = cm_j = i; }

if(cur_max > max){ m_i = cm_i; m_j = cm_j;

max = cur_max; }

}

return new int[] {m_i, m_j, max}; }

public static void main(String[] args) { int[] a = new int[]{31, -41, 59, 26, -53, 58, 97, -93, -23, 84}; int[] ijmax = maxsum(5, a.length -1, a); System.out.printf("i=%d, j=%d, sum=%d\n", ijmax[0], ijmax[1], ijmax[2]); }

}

Retrieved from "https://algorist.com/algowiki_v2/index.php?title=TADM2E_8.25&oldid=228"