Re: Minimum sub-sequence sum

Hi David,

On Jul 21, 8:49 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
wrote:
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.)


Its not a homework problem but rather an interview question I
encountered a few months ago, I take your point that investigating it
on my own would be far more beneficial.


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


I hope I can! :)

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?

I can see how these two simpler problems would be solved using an
O(n^2) complex algorithm, I am going to consider using a DP style
approach, and somehow remember sums for specific ranges.

Thanks for the insight, I'll post back if I have anymore difficulties



-Mich
.

Relevant Pages

  • Re: Is there a polynomial algorithm for that problem?
    ... The sum over all n numbers is negative. ... Unfortunately that algorithm does not scale. ... An instance of 3-Partition consists of a list of 3m positive integers ... list can be partitioned into m lists of size 3, ...
    (sci.math)
  • Re: Choose k random lines from file
    ... > What, for the algorithm shown above, or for any algorithm? ... Yes, that is an unbiased generator, but I had thought ... >>give less of a bias using an extra float or double ... >>distribution for the sum. ...
    (comp.programming)
  • Re: standard deviation, but without the mean
    ... Suppose Xsum is the sum of the the first n numbes and that X2 is ... Just keep track if X2 and Xsum as you go. ... Actually this is not a correct algorithm, ... the error in the least 9 digits.. ...
    (sci.stat.math)
  • Re: C# generic containers from a "C++ perspective"
    ... If you implement the floating-point and integer algorithms ... Maintain the sum of all the items in an accumulator. ... That is the fundamentally-broken algorithm that I was expecting you to ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Disjoint circle merge NP complete for L^n error?
    ... The key point is that we need to be sure there is no optimal algorithm ... We only need to erase MAX and replace with SUM in the proof ... minimum error partition) algorithm in P. ... MAX. I'm pretty sure that if both these are in NP then all L^n metrics ...
    (comp.theory)