Re: Minimum sub-sequence sum
- From: Gerry Myerson <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Tue, 22 Jul 2008 05:46:22 GMT
In article
<9b537cf5-5864-499c-8da0-d9e9c442f438@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Michael Jarrod <Michael.Jarrod@xxxxxxxxx> 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?
Call your integers a_1, a_2, ..., a_n.
Compute the numbers
s_1 = a_1,
s_2 = a_1 + a_2,
....
s_n = a_1 + a_2 + ... + a_n.
That much should only take O(n) operations.
Now calculate all the numbers s_i - s_j with i > j,
and keep track of which of them is the smallest.
That's O(n^2), and you're done.
--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.
- References:
- Minimum sub-sequence sum
- From: Michael Jarrod
- Minimum sub-sequence sum
- Prev by Date: Re: computational complexity of Euclid's algorithm
- Next by Date: Re: computational complexity of Euclid's algorithm
- Previous by thread: Minimum sub-sequence sum
- Next by thread: Hyperbolic Geometry book recommendation please
- Index(es):
Relevant Pages
|
