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

Published on 12 May 2024 09:40 PM
#Coffeescript

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

Source code in the coffeescript programming language

max_sum_seq = (sequence) ->
  # This runs in linear time.
  [sum_start, sum, max_sum, max_start, max_end] = [0, 0, 0, 0, 0]
  for n, i in sequence
    sum += n
    if sum > max_sum
      max_sum = sum
      max_start = sum_start
      max_end = i + 1
    if sum < 0 # start new sequence
      sum = 0
      sum_start = i + 1
  sequence[max_start...max_end]
  
# tests
console.log max_sum_seq [-1, 0, 15, 3, -9, 12, -4]
console.log max_sum_seq [-1]
console.log max_sum_seq [4, -10, 3]

You may also check:How to resolve the algorithm Sierpinski pentagon step by step in the Action! programming language
You may also check:How to resolve the algorithm Arrays step by step in the XLISP programming language
You may also check:How to resolve the algorithm User input/Text step by step in the R programming language
You may also check:How to resolve the algorithm Number reversal game step by step in the APL programming language
You may also check:How to resolve the algorithm Dutch national flag problem step by step in the Swift programming language