Re: Minimum sub-sequence sum
- From: Bryan Olson <fakeaddress@xxxxxxxxxxx>
- Date: Thu, 24 Jul 2008 01:08:36 -0700
grpadmin@xxxxxxxxx wrote:
Michael Jarrod wrote:I have a sequence of integers (positive/negative values) and I would
like to find the sub sequence of consecutive values that yields the
smallest sum, I can think of a very simple O(n^3) complex solution,
however I was wondering are there any better solutions? and what is
the name of this kind of problem?
Jon Bentley uses a problem like this in one of his Programming Pearls
columns. There are
subquadratic algorithms as well as two quadratic algorithms he
considers. You might try a
divide-and-conquer approach and also a tail-recursive (read: clever
iterative) approach to get
a subquadratic runtime. Surprisingly, the quickest solution needs
little memoization if any.
If you can't come up with it on your own (or even if you can), check
out the collections (two
that I know) of Programming Pearls by the above author.
It's in the first collection, /Programming Pearls/. First edition 1986,
second 2000.
http://www.amazon.com/Programming-Pearls-2nd-ACM-Press/dp/0201657880
--
--Bryan
.
- References:
- Minimum sub-sequence sum
- From: Michael Jarrod
- Re: Minimum sub-sequence sum
- From: grpadmin
- Minimum sub-sequence sum
- Prev by Date: very very interesting
- Next by Date: CFP/Bursary Awards - InnovationWell Autumn Community of Practice Meeting
- Previous by thread: Re: Minimum sub-sequence sum
- Next by thread: Re: Minimum sub-sequence sum
- Index(es):
Relevant Pages
|
