19 lines
536 B
Plaintext
19 lines
536 B
Plaintext
F maxsumseq(sequence)
|
|
V (start, end, sum_start) = (-1, -1, -1)
|
|
V (maxsum_, sum_) = (0, 0)
|
|
L(x) sequence
|
|
sum_ += x
|
|
I maxsum_ < sum_
|
|
maxsum_ = sum_
|
|
(start, end) = (sum_start, L.index)
|
|
E I sum_ < 0
|
|
sum_ = 0
|
|
sum_start = L.index
|
|
assert(maxsum_ == sum(sequence[start + 1 .. end]))
|
|
R sequence[start + 1 .. end]
|
|
|
|
print(maxsumseq([-1, 2, -1]))
|
|
print(maxsumseq([-1, 2, -1, 3, -1]))
|
|
print(maxsumseq([-1, 1, 2, -5, -6]))
|
|
print(maxsumseq([-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]))
|