How to resolve the algorithm Greatest subsequential sum step by step in the Arturo programming language

Published on 12 May 2024 09:40 PM
#Arturo

How to resolve the algorithm Greatest subsequential sum step by step in the Arturo 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 Arturo programming language

Source code in the arturo programming language

subarraySum: function [arr][
    curr: 0
    mx: 0
    fst: size arr
    lst: 0
    currFst: 0

    loop.with: 'i arr [e][
        curr: curr + e
        if e > curr [
            curr: e
            currFst: i
        ]
        if curr > mx [
            mx: curr
            fst: currFst
            lst: i
        ]
    ]
    if? lst > fst -> return @[mx, slice arr fst lst]
    else -> return [0, []]
]

sequences: @[
    @[1, 2, 3, 4, 5, neg 8, neg 9, neg 20, 40, 25, neg 5]
    @[neg 1, neg 2, 3, 5, 6, neg 2, neg 1, 4, neg 4, 2, neg 1]
    @[neg 1, neg 2, neg 3, neg 4, neg 5]
    @[]
]

loop sequences 'seq [
    print [pad "sequence:" 15 seq]
    processed: subarraySum seq
    print [pad "max sum:" 15 first processed]
    print [pad "subsequence:" 15 last processed "\n"]
]

You may also check:How to resolve the algorithm Wagstaff primes step by step in the RPL programming language
You may also check:How to resolve the algorithm Loops/For step by step in the Scilab programming language
You may also check:How to resolve the algorithm Stern-Brocot sequence step by step in the C++ programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the PL/I programming language
You may also check:How to resolve the algorithm Variable size/Get step by step in the REXX programming language