Re: Minimum sub-sequence sum

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?

Yes, there are better algorithms. This is a classic homework problem
in algorithms. Are you taking an algorithms course? Is this is a
homework problem?

Rather than telling you the answer, I will let you have the experience
of finding the algorithm yourself -- algorithms is an area that is best
learnt by solving algorithm design problems yourself rather than just
looking up the solution at the back of the book. (While the process of
searching for a better algorithm yourself can be frustrating and painful,
it's the best way I know to learn the subject.)

You should find it very easy to design a O(n^2) algorithm. But can
you do even better?

If you're stuck, here are some warmup problems to consider that may help.
Suppose you wanted to find the prefix of your sequence that yields the
smallest sum. In other words, this is a variant of your problem where
we only consider consecutive subsequences that include the start of the
original sequence (i.e., we look for a value i such that the sum of the
elements at indices 0,1,..,i gives the smallest possible sum). How fast
could you do it? What about another variant where you are given the
original sequence and also a number j, and want to find the value i such
that the sum of the elements at indices 0,1,..,i is minimized? How fast
can you do it? Suppose you wanted to compute the solution to the latter
problem for every value of j (so that the output of your algorithm is
N answers, one for each possible value of j)? How fast can you do that?
.

Relevant Pages

  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)
  • Re: * says: Definition: sum{i in N} i = 0
    ... "Divergent series" means: ... is the sum of its terms, ... underlying infinite sequence _if_ the limit exists. ... Euler has literally written is not proved true. ...
    (sci.math)
  • Re: an true information theory
    ... > outputs, and figures out that the algorithm must be A1, there ... > there is an infinite number of stages n such that P's guess at ... > sequence of algorithms, strike off every algorithm that appears ... I've read that quantum computing may improve tractability but ...
    (sci.math)
  • Re: Synthesis of Concurrent Statements for FIR Filter
    ... the convolution in VHDL. ... and -1's and convolved with the impulse sequence 'h'. ... into sum AND THEN put the 'sum' result into 'y'. ... What you have written contains 0 multipliers, 15 x 2-1 muxes, no ...
    (comp.lang.vhdl)
  • Re: * says: Definition: sum{i in N} i = 0
    ... "Divergent series" means: ... is the sum of its terms, then you get the result that a divergent ... that the infinite sequence of naturals is divergent in N. ... _you_ impute that Euler literally has written. ...
    (sci.math)