Re: Minimum sub-sequence sum

Michael Jarrod <Michael.Jarrod@xxxxxxxxx> writes:

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?

Your O(n^3) gets another n from each of:

1. Try different positions for the start of the subsequence
2. Try different positions for the end of the subsequence
3. Calculating the sum of a subsequence

to make the O(n^3)?

Mark
.

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, ... subquadratic algorithms as well as two quadratic algorithms he ...
    (comp.theory)
  • 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, ...
    (sci.math)
  • 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)