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

Published on 12 May 2024 09:40 PM
#F_Sharp

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

Source code in the fsharp programming language

let maxsubseq s =
    let (_, _, maxsum, maxseq) =
        List.fold (fun (sum, seq, maxsum, maxseq) x ->
            let (sum, seq) = (sum + x, x :: seq)
            if sum < 0 then (0, [], maxsum, maxseq)
            else if sum > maxsum then (sum, seq, sum, seq)
            else (sum, seq, maxsum, maxseq))
            (0, [], 0, []) s
    List.rev maxseq

printfn "%A" (maxsubseq  [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1])

You may also check:How to resolve the algorithm Echo server step by step in the C# programming language
You may also check:How to resolve the algorithm Closures/Value capture step by step in the C++ programming language
You may also check:How to resolve the algorithm Permutations step by step in the Erlang programming language
You may also check:How to resolve the algorithm Sparkline in unicode step by step in the Clojure programming language
You may also check:How to resolve the algorithm Last Friday of each month step by step in the Raku programming language