cef@h.gp.cs.cmu.edu (Charles Fineman) (01/06/89)
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
-- kornellm@cpsc.ucalgary.ca (Mark Kornell) (01/06/89)
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 < ================================================================================
cef@h.gp.cs.cmu.edu (Charles Fineman) (01/07/89)
) 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 ) Ooops... The above formulation seemed to cause problems locally so I'm posting a clarification (some people are so _literal_ :-). We are looking for the maximal sub-STRING that is a maximal subsequence whose terms are continguous in the original sequence. One other point... There are two possible ways to look at the problem (both are perfectly acceptable interpretations, the code will be almost identical). Some solutions return the empty string if there are no positive terms in the sequence. This is certainly valid (as the empty sumantion is defined to be zero which is greater than an negative number). One could also write the algorithm to return the maximal NON-EMPTY sub-string. --