Subj : Re: question about finding sum of subset of contiguos elements of
To   : comp.programming
From : August Karlstrom
Date : Tue Oct 11 2005 12:59 am

Willem wrote:
> Richard wrote:
> ) Given the subject line it is almost certain that he means subset of
> ) contiguous elements.  Shouldn't there be a limit to nit-picking?
> 
> Aww, lemme have a bit of fun with them CS-101 students. :-)
> 
> Anyway, one possible O(n) solution I can think of needs O(n) extra memory,
> for an auxiliary array.  I can't think of a solution offhand that doesn't.
> That doesn't mean there isn't one, of course, it just means it's been too
> long since my days in CS class, and I have to use my big thumb instead. :)

We simply calculate the partial sums (from the beginning) and return the 
maximum difference, all in one loop. Here is an O(n) time, O(1) space 
algorithm implemented in Oberon:

    PROCEDURE MaxSubarraySum*(VAR (*in*) a: ARRAY OF LONGINT): LONGINT;
       VAR k, min, max, sum, result: LONGINT;

       PROCEDURE UpdateResult;
       BEGIN
          IF (min < 0) & (max - min > result) THEN result := max - min
          ELSIF max > result THEN result := max
          END
       END UpdateResult;

    BEGIN
       min := a[0]; max := a[0]; sum := a[0]; result := a[0];
       FOR k := 1 TO LEN(a) - 1 DO
          INC(sum, a[k]);
          IF sum < min THEN UpdateResult; min := sum; max := min
          ELSIF sum > max THEN max := sum
          END
       END;
       UpdateResult;
       RETURN result
    END MaxSubarraySum;


August

.