How to resolve the algorithm Greatest subsequential sum step by step in the Potion programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Greatest subsequential sum step by step in the Potion programming language
Table of Contents
Problem Statement
Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements, that is, the elements of no other single subsequence add up to a value larger than this one.
An empty subsequence is considered to have the sum of 0; thus if all elements are negative, the result must be the empty sequence.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Greatest subsequential sum step by step in the Potion programming language
Source code in the potion programming language
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))
You may also check:How to resolve the algorithm Even or odd step by step in the 11l programming language
You may also check:How to resolve the algorithm Jaro similarity step by step in the Raku programming language
You may also check:How to resolve the algorithm Execute Brain step by step in the BCPL programming language
You may also check:How to resolve the algorithm Fast Fourier transform step by step in the Rust programming language
You may also check:How to resolve the algorithm Word wrap step by step in the Seed7 programming language