Re: Minimum sub-sequence sum

On Jul 21, 8:13 pm, Michael Jarrod <Michael.Jar...@xxxxxxxxx> wrote:
Hello,

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?

-Mich

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.

Gerhard Paseman, 2008.07.23
.

Relevant Pages

  • Re: Minimum sub-sequence sum
    ... like to find the sub sequence of consecutive values that yields the ... smallest sum, I can think of a very simple Ocomplex solution, ...
    (comp.programming)
  • Re: Minimum sub-sequence sum
    ... like to find the sub sequence of consecutive values that yields the ... smallest sum, I can think of a very simple Ocomplex solution, ... subsequence of values that are consecutive integers? ...
    (comp.theory)
  • Minimum sub-sequence sum
    ... like to find the sub sequence of consecutive values that yields the ... smallest sum, I can think of a very simple Ocomplex solution, ...
    (comp.programming)
  • Minimum sub-sequence sum
    ... like to find the sub sequence of consecutive values that yields the ... smallest sum, I can think of a very simple Ocomplex solution, ...
    (comp.theory)
  • Minimum sub-sequence sum
    ... like to find the sub sequence of consecutive values that yields the ... smallest sum, I can think of a very simple Ocomplex solution, ...
    (sci.math)