Greatest subsequential sum: Difference between revisions
Content added Content deleted
(→{{header|Prolog}}: added simpler second example.) |
(→{{header|Potion}}: Added potion solution) |
||
Line 2,187: | Line 2,187: | ||
3 5 6 -2 -1 4 |
3 5 6 -2 -1 4 |
||
Sum: 15 |
Sum: 15 |
||
</pre> |
</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}}== |
=={{header|Prolog}}== |