Anonymous user
Greatest subsequential sum: Difference between revisions
→{{header|Potion}}: Added potion solution
(→{{header|Prolog}}: added simpler second example.) |
(→{{header|Potion}}: Added potion solution) |
||
Line 2,187:
3 5 6 -2 -1 4
Sum: 15
</pre>
=={{header|Potion}}==
<lang potion>gss = (lst) :
# Find discrete integral
integral = (0)
accum = 0
lst each (n): accum = accum + n, integral append(accum).
# Check integral[b + 1] - integral[a] for all 0 <= a <= b < N
max = -1
max_a = 0
max_b = 0
lst length times (b) :
b times (a) :
if (integral(b + 1) - integral(a) > max) :
max = integral(b + 1) - integral(a)
max_a = a
max_b = b
.
.
.
# Print the results
if (max >= 0) :
(lst slice(max_a, max_b) join(" + "), " = ", max, "\n") join print
.
else :
"No subsequence larger than 0\n" print
.
.
gss((-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))
gss((-1, -2, -3, -4, -5))
gss((+7,-6,-8,+5,-2,-6,+7,+4,+8,-9,-3,+2,+6,-4,-6))</lang>
<pre>
3 + 5 + 6 + -2 + -1 + 4 = 15
No subsequence larger than 0
7 + 4 + 8 = 19
</pre>
=={{header|Prolog}}==
| |||