Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!nrl-cmf!ukma!rutgers!rochester!pt.cs.cmu.edu!h.gp.cs.cmu.edu!cef
From: cef@h.gp.cs.cmu.edu (Charles Fineman)
Newsgroups: comp.lang.c
Subject: Name that algorithm (a small puzzle)
Message-ID: <3968@pt.cs.cmu.edu>
Date: 5 Jan 89 17:25:36 GMT
Organization: Carnegie-Mellon University, CS/RI
Lines: 16

A friend showed me a interestng problem the other day. In light of
the interest in the 2^n celing problem a couple of months ago, I 
thought y'all might be interested...

    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. 

I will post my solution in a few days if there is sufficient interest.

	Charlie Fineman


--