Greatest subsequential sum: Difference between revisions
→{{header|Python}}: Added a functional version - a linear derivation of sum and sequence together, in terms of reduce.
m (→JS Functional) |
(→{{header|Python}}: Added a functional version - a linear derivation of sum and sequence together, in terms of reduce.) |
||
Line 2,545:
=={{header|Python}}==
===Imperative===
Naive, inefficient but really simple solution which tests all possible subsequences, as in a few of the other examples:
<lang python>def maxsubseq(seq):
Line 2,608 ⟶ 2,609:
assert f([-1, 2, -1, 3, -1]) == [2, -1, 3]
assert f([-1, 1, 2, -5, -6]) == [1,2]</lang>
===Functional===
We can efficiently derive sum and sequence together, without mutation, using '''reduce''' to express a linear accumulation over a fold:
<lang python>from functools import (reduce)
# maxSubseq :: [Int] -> [Int] -> (Int, [Int])
def maxSubseq(xs):
def go(ab, x):
(m1, m2) = ab[0]
high = max((0, []), (m1 + x, m2 + [x]))
return (high, max(ab[1], high))
return reduce(go, xs, ((0, []), (0, [])))[1]
print(
maxSubseq(
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
)
)</lang>
{{Out}}
<pre>(15, [3, 5, 6, -2, -1, 4])</pre>
=={{header|R}}==
| |||