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

Published on 12 May 2024 09:40 PM
#Factor

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

Source code in the factor programming language

USING: kernel locals math math.order sequences ;

:: max-with-index ( elt0 ind0 elt1 ind1 -- elt ind )
elt0 elt1 <  [ elt1 ind1 ] [ elt0 ind0 ] if ;
: last-of-max ( accseq -- ind ) -1 swap -1 [ max-with-index ] reduce-index nip ;

: max-subseq ( seq -- subseq )
dup 0 [ + 0 max ] accumulate swap suffix last-of-max head
dup 0 [ + ] accumulate swap suffix [ neg ] map last-of-max tail ;


( scratchpad ) { -1 -2 3 5 6 -2 -1 4 -4 2 -1 } max-subseq  dup sum  swap . .
{ 3 5 6 -2 -1 4 }
15

You may also check:How to resolve the algorithm Reverse a string step by step in the SNOBOL4 programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the i programming language
You may also check:How to resolve the algorithm Checkpoint synchronization step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Roman numerals/Encode step by step in the Cowgol programming language
You may also check:How to resolve the algorithm Even or odd step by step in the 8th programming language