Path: utzoo!utgpu!attcan!uunet!lll-winken!lll-lcc!ames!pasteur!ucbvax!decwrl!labrea!rutgers!att!alberta!calgary!cpsc!kornellm
From: kornellm@cpsc.ucalgary.ca (Mark Kornell)
Newsgroups: comp.lang.c
Subject: Re: Name that algorithm (a small puzzle)
Summary: CACM
Message-ID: <450@cs-spool.calgary.UUCP>
Date: 6 Jan 89 01:31:08 GMT
References: <3968@pt.cs.cmu.edu>
Sender: news@calgary.UUCP
Lines: 26

In article <3968@pt.cs.cmu.edu>, cef@h.gp.cs.cmu.edu (Charles Fineman) writes:
 >     Let a sequence of integers be given. Define a "maximal"
 >   sub-string to be a sub-string whose sum is the greatest
 >   of all sub-strings (there could be more than one).
 > 
 >     Find the cheapest (time-wise) algorithm that will find a
 >   "maximal" subsequence and return its range and sum. 
 > 
 > 	Charlie Fineman


Several algorithms to do this task were developed and compared in the CACM
column, "Programming Pearls", in Volume 27, Number 9 (Sept 84), pp. 865 - 
871.

The algorithms ranged from a cubic (on the length of the sequence) algorithm
to a linear algorithm.

The algorithms given only computed the sum of the maximum sub-range, and did
not return the range itself.  However, it would be trivial to keep track of
this information.

> The meek shall inherit the earth --  |    Mark Kornell                       <
>   in plots 6 feet by 3 feet          |       kornellm@cpsc.UCalgary.CA       <
>   (but they do get mineral rights)   |       Kornell@UNCAMULT                <
================================================================================