Re: Minimum sub-sequence sum
- From: Hallvard B Furuseth <h.b.furuseth@xxxxxxxxxxx>
- Date: Tue, 22 Jul 2008 09:02:09 +0200
Michael Jarrod 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?
O(n): Walk through the sequence once, tracking whether the last negative
number should be included in the answer if the next negative number is.
def minsum_seq(seq):
total, found_total, found, seq = 0, 0, (0, -1), list(seq)
for index_of_val, val in enumerate(seq):
if total >= 0:
start_index, total = index_of_val, val
else:
total += val
if total < found_total:
found_total, found = total, (start_index, index_of_val)
return seq[found[0] : found[1] + 1]
--
Hallvard
.
- References:
- Minimum sub-sequence sum
- From: Michael Jarrod
- Minimum sub-sequence sum
- Prev by Date: Re: Algorithm or method for finding maximum of a long polynomial
- Next by Date: A Call for Reassessment
- Previous by thread: Minimum sub-sequence sum
- Next by thread: Algorithm or method for finding maximum of a long polynomial
- Index(es):
Relevant Pages
|
