Greatest subsequential sum: Difference between revisions

{{trans|Python}}

 

V (start, end, sum_start) = (-1, -1, -1)

V (maxsum_, sum_) = (0, 0)

print(maxsumseq([-1, 2, -1, 3, -1]))

print(maxsumseq([-1, 1, 2, -5, -6]))

 

{{out}}

 

=={{header|Action!}}==

INT i

 

Process(c,5)

Process(d,0)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Greatest_subsequential_sum.png Screenshot from Atari 8-bit computer]

 

=={{header|Ada}}==

 

procedure Max_Subarray is

when Empty_Error =>

Put_Line("Array being analyzed has no elements.");

 

=={{header|Aime}}==

{

integer e, f, i, sum;

 

0;

{{Out}}

<pre>Max sum 15

{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d]}}

(

[]INT a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);

OD

 

{{out}}

<pre>

{{Trans|Haskell}}

Linear derivation of both sum and list, in a single fold:

on maxSubseq(xs)

script go

on Tuple(a, b)

{type:"Tuple", |1|:a, |2|:b, length:2}

{{Out}}

<pre>{15, {3, 5, 6, -2, -1, 4}}</pre>

=={{header|Arturo}}==

 

curr: 0

mx: 0

print [pad "max sum:" 15 first processed]

print [pad "subsequence:" 15 last processed "\n"]

 

{{out}}

 

=={{header|ATS}}==

(*

** This one is

//

} (* end of [main0] *)

{{out}}

<pre>

=={{header|AutoHotkey}}==

classic algorithm:

max := sum := start := 0

Loop Parse, seq, `,

Loop Parse, seq, `,

s .= A_Index > a && A_Index <= b ? A_LoopField "," : ""

 

=={{header|AutoIt}}==

Local $iArray[11] = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]

GREAT_SUB($iArray)

ConsoleWrite("]" & @CRLF & "!>SUM of subsequence: " & $iSUM & @CRLF)

EndFunc ;==>GREAT_SUB

 

{{out}}

=={{header|AWK}}==

{{trans|Common Lisp}}

# Sets subseq[1] to subseq[n] and returns n. Also sets subseq["sum"].

# An empty subsequence has sum 0.

subseq["sum"] = b

return bn

 

function join(ary, len, i, s) {

s = "["

try("0 1 2 -3 3 -1 0 -4 0 -1 -4 2")

try("-1 -2 3 5 6 -2 -1 4 -4 2 -1")

 

{{out}}

 

=={{header|BBC BASIC}}==

PRINT FNshowarray(A%()) " -> " FNmaxsubsequence(A%())

DIM B%(10) : B%() = -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1

a$ += STR$(a%(i%)) + ", "

NEXT

{{out}}

<pre>

This program iterates over all subsequences by forced backtracking, caused by the failing node <code>~</code> at the end of the middle part of the pattern. The combination of flags <code>[%</code> on an expression creates a pattern that succeeds if and only if the expression is successfully evaluated. <code>sjt</code> is an extra argument to any function that is part of a pattern and it contains the current subexpression candidate. Inside the pattern the function <code>sum</code> sums over all elements in <code>sjt</code>. The currently longest maximal subsequence is kept in <code>seq</code>.

 

( 0:?max

& :?seq

| !seq

)

 

<pre>3 5 6 -2 -1 4</pre>

 

=={{header|C}}==

 

typedef struct Range {

 

return 0;

{{out}}

<pre>Max sum = 15

=={{header|C sharp|C#}}==

'''The challange'''

 

namespace Tests_With_Framework_4

}

}

 

=={{header|C++}}==

#include <iterator> // for std::iterator_traits

#include <iostream> // for std::cout

 

return 0;

 

=={{header|Clojure}}==

{{trans|Haskell}}

Naive algorithm:

(->> (take-while seq (iterate rest coll)) ; tails

(mapcat #(reductions conj [] %)) ; inits

 

{{out}}

 

=={{header|CoffeeScript}}==

max_sum_seq = (sequence) ->

# This runs in linear time.

console.log max_sum_seq [-1]

console.log max_sum_seq [4, -10, 3]

 

=={{header|Common Lisp}}==

Returns the maximum subsequence sum, the subsequence with the maximum sum, and start and end indices for the subsequence within the original sequence. Based on the implementation at [http://wordaligned.org/articles/the-maximum-subsequence-problem Word Aligned]. Leading zeroes aren't trimmed from the subsequence.

 

(let ((best-sum 0) (current-sum 0) (end 0))

;; determine the best sum, and the end of the max subsequence

(sum sum (- sum (first sublist))))

((or (endp sublist) (eql sum best-sum))

 

For example,

{{trans|PicoLisp}}

 

(loop for subsequence in (mapcon (lambda (x) (maplist #'reverse (reverse x))) seq)

for sum = (reduce #'+ subsequence :initial-value 0)

maximizing sum into max

if (= sum max) do (setf max-subsequence subsequence)

 

=={{header|Component Pascal}}==

Works with BlackBox Component Builder

MODULE OvctGreatestSubsequentialSum;

IMPORT StdLog, Strings, Args;

 

END OvctGreatestSubsequentialSum.

Execute: <br/>

<pre>

{{trans|Ruby}}

Answer is stored in "slice". It is very slow O(n**3)

max, slice = 0, [] of Int32

arr.each_index do |i|

end

[max, slice]

 

===Linear Time Version:===

A better answer would run in O(n) instead of O(n**2) using numerical properties to remove the need for the inner loop.

 

# in the iteration if starting a new chain is

# better than your current score with this element

end

return max, arr[first..last]

 

'''Test:'''

[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],

[-1, -2, -3, -4, -5],

puts "\nInput seq: #{input}"

puts " Max sum: %d\n Subseq: %s" % subarray_sum(input)

{{out}}

<pre>

=={{header|D}}==

{{trans|Python}}

 

inout(T[]) maxSubseq(T)(inout T[] sequence) pure nothrow @nogc {

const a2 = [-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1];

writeln("Maximal subsequence: ", a2.maxSubseq);

{{out}}

<pre>Maximal subsequence: [3, 5, 6, -2, -1, 4]

and max can't be used as the maximumBy functions

(for the concatMap a map.join is enough).

 

mixin template InitsTails(T) {

[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1].maxSubseq.writeln;

[-1, -2, -3, -5, -6, -2, -1, -4, -4, -2, -1].maxSubseq.writeln;

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/Greatest_subsequential_sum#Pascal Pascal].

<code>maxSubseq</code> returns both the maximum sum found, and the interval of indexes which produces it.

 

 

def maxSubseq(seq) {

return ["value" => maxValue,

"indexes" => maxInterval]

 

def [=> value, => indexes] := maxSubseq(seq)

println(`$\

Indexes: ${indexes.getOptStart()}..${indexes.getOptBound().previous()}

Subsequence: ${seq(indexes.getOptStart(), indexes.getOptBound())}

 

=={{header|EchoLisp}}==

(lib 'struct)

(struct result (score starter))

(max-seq L)

→ (15 (3 5 6 -2 -1 4))

 

=={{header|Elixir}}==

{{trans|Ruby}}

===Linear Time Version:===

def subseq_sum(list) do

list_i = Enum.with_index(list)

{max, Enum.slice(list, first..last)}

end

Output is the same above.

 

===Brute Force:===

def subseq_sum(list) do

limit = length(list) - 1

end)

end

 

'''Test:'''

[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],

[-1, -2, -3, -4, -5],

{max, subseq} = Greatest.subseq_sum(input)

IO.puts " Max sum: #{max}\n Subseq: #{inspect subseq}"

 

{{out}}

 

=={{header|ERRE}}==

PROGRAM MAX_SUM

 

!$ERASE P%

END PROGRAM

 

=={{header|Euler Math Toolbox}}==

The following recursive system seems to have a run time of O(n), but it needs some copying, so the run time is really O(n^2).

 

>function %maxsubs (v,n) ...

$if n==1 then

>maxsubs([-1, -2, -3, -4, -5])

Empty matrix of size 1x0

 

Here is a brute force method producing and testing all sums. The runtime is O(n^3).

 

>function maxsubsbrute (v) ...

$ n=cols(v);

>maxsubsbrute([-1, -2, -3, -4, -5])

Empty matrix of size 1x0

 

To see, if everything works, the following tests on 10 million random sequences.

 

>function test ...

$ loop 1 to 10000000

$ endfunction

>test

 

=={{header|Euphoria}}==

integer sum, maxsum, first, last

maxsum = 0

? maxSubseq({-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1})

? maxSubseq({})

 

{{out}}

 

=={{header|F_Sharp|F#}}==

let (_, _, maxsum, maxseq) =

List.fold (fun (sum, seq, maxsum, maxseq) x ->

List.rev maxseq

 

{{out}}

<pre>[3; 5; 6; -2; -1; 4]</pre>

 

=={{header|Factor}}==

 

:: max-with-index ( elt0 ind0 elt1 ind1 -- elt ind )

: max-subseq ( seq -- subseq )

dup 0 [ + 0 max ] accumulate swap suffix last-of-max head

{ 3 5 6 -2 -1 4 }

 

=={{header|Forth}}==

variable best-sum

 

 

create test -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1 ,

{{out}}

 

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

implicit none

 

print *, a(m(1):m(2))

 

 

=={{header|FreeBASIC}}==

 

Dim As Integer seq(10) = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1}

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|Go}}==

 

import "fmt"

fmt.Println("Sum: ", sum, "\n")

}

{{out}}

<pre>

=={{header|Haskell}}==

Naive approach which tests all possible subsequences, as in a few of the other examples. For fun, this is in point-free style and doesn't use loops:

import Data.Ord (comparing)

 

maxsubseq = maximumBy (comparing sum) . subseqs

 

Secondly, the linear time constant space approach:

maxSubseq =

let go x ((h1, h2), sofar) =

 

main :: IO ()

{{Out}}

<pre>(15,[3,5,6,-2,-1,4])</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

L1 := [-1,-2,3,5,6,-2,-1,4,-4,2,-1] # sample list

L := [-1,1,2,3,4,-11]|||L1 # prepend a local maximum into the mix

}

return L[(\maxglobalI)[1]:maxglobalI[2]] | [] # return sub-sequence or empty list

 

=={{header|IS-BASIC}}==

110 RANDOMIZE

120 NUMERIC A(1 TO 15)

290 PRINT A(I);

300 NEXT

 

=={{header|J}}==

AS =. 0,; <:/~@i.&.> #\y

MX =. (= >./) AS +/ . * y

y #~ {. MX#AS

 

<tt>y</tt> is the input vector, an integer list.<br>

If zero is the maximal sum the empty array is always returned, although sub-sequences of positive length (comprised of zeros) might be more interesting.<br>

Example use:

 

Note: if we just want the sum of the maximum subsequence,

and are not concerned with the subsequence itself, we can use:

 

 

Example use:

 

This suggests a variant:

sums=: (0>.+)/\. y

start=: sums i. max=: >./ sums

max (] {.~ #@] |&>: (= +/\) i. 1:) y}.~start

or

start=. (i. >./) (0>.+)/\. y

({.~ # |&>: [: (i.>./@,&0) +/\) y}.~start

 

These variants are considerably faster than the first implementation, on long sequences.

 

The method <tt>nextChoices</tt> was modified from an [http://www.cs.rit.edu/~vcss233/Labs/newlab02/index.html RIT CS lab].

import java.util.ArrayList;

 

return false;

}

 

This one runs in linear time, and isn't generalized.

int sum = 0;

int maxsum = 0;

}

return maxsum;

 

=={{header|JavaScript}}==

===Imperative===

Simple brute force approach.

var maxValue = 0;

var subsequence = [];

}

return result;

 

===Functional===

{{Trans|Haskell}}

Linear approach, deriving both list and sum in a single accumulating fold.

 

// maxSubseq :: [Int] -> (Int, [Int])

// MAIN ---

return main();

{{Out}}

<pre>[3,5,6,-2,-1,4] -> 15</pre>

 

This is the same linear-time algorithm as used in the [[#Ruby]] subsection on this page.

. as $arr

| reduce range(0; length) as $i

else .

end)

'''Example''':

{{out}}

 

=={{header|Jsish}}==

From Javascript entry.

function sumValues(arr) {

var result = 0;

greatestSubsequentialSum(gss) ==> [ 15, [ 3, 5, 6, -2, -1, 4 ] ]

=!EXPECTEND!=

 

{{out}}

{{works with|Julia|0.6}}

 

smax = hmax = tmax = 0

for head in eachindex(arr), tail in head:length(arr)

s = sum(subseq)

 

 

{{out}}

 

=={{header|Kotlin}}==

 

fun gss(seq: IntArray): Triple<Int, Int, Int> {

else

println("Maximum subsequence is the empty sequence which has a sum of 0")

 

{{out}}

 

=={{header|Liberty BASIC}}==

'Greatest_subsequential_sum

 

print

end sub

 

=={{header|Lua}}==

function maxsub(ary, idx)

local idx = idx or 1

for i = idx, last do ret[#ret+1] = ary[i] end

return ret

 

=={{header|M4}}==

define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,

incr($2),shift(shift(shift($@))))')')

`define(`maxsum',sum)`'define(`xmax',x)`'define(`ymax',y)')')')

divert

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

===Method 1===

First we define 2 functions, one that gives all possibles subsequences (as a list of lists of indices) for a particular length. Then another extract those indices adds them up and looks for the largest sum.

MaximumSubsequence[x_List]:=Module[{sums},

sums={x[[#]],Total[x[[#]]]}&/@Sequences[Length[x]];

First[First[sums[[Ordering[sums,-1,#1[[2]]<#2[[2]]&]]]]]

 

===Method 2===

 

===Examples===

MaximumSubsequence[{2,4,5}]

MaximumSubsequence[{2,-4,3}]

MaximumSubsequence[{4}]

gives back:

<pre>{3,5,6,-2,-1,4}

=={{header|Mathprog}}==

see [[wp:Special_ordered_set]]. Lmin specifies the minimum length of the required subsequence, and Lmax the maximum.

/*Special ordered set of type N

 

 

end;

 

produces:

 

GLPSOL: GLPK LP/MIP Solver, v4.47

Parameter(s) specified in the command line:

Model has been successfully processed

 

 

=={{header|MATLAB}} / {{header|Octave}}==

% Greatest subsequential sum

a =[0;a(:);0]';

end;

GS = a(ix1(K)+1:ix2(K));

 

Usage:

 

=={{header|NetRexx}}==

* 10.08.2012 Walter Pachl Pascal algorithm -> Rexx -> NetRexx

**********************************************************************/

Say ol

Say 'Sum:' maxSum

Output: the same as for Rexx

 

=={{header|Nim}}==

var maxendinghere = 0

for x in s:

result = max(result, maxendinghere)

 

 

{{out}}

=={{header|Oberon-2}}==

Works with oo2c Version 2

MODULE GreatestSubsequentialSum;

IMPORT

END GreatestSubsequentialSum.

 

Execute:<br/>

<pre>

 

=={{header|OCaml}}==

let rec loop sum seq maxsum maxseq = function

| [] -> maxsum, List.rev maxseq

 

let _ =

 

This returns a pair of the maximum sum and (one of) the maximum subsequence(s).

 

=={{header|Oz}}==

fun {MaxSubSeq Xs}

 

end

in

 

=={{header|PARI/GP}}==

Naive quadratic solution (with end-trimming).

my(mn=1,mx=#v,r=0,at,c);

if(vecmax(v)<=0,return([1,0]));

);

at

 

=={{header|Pascal}}==

 

var

writeln ('Sum:');

writeln (maxSum);

{{out}}

<pre>:> ./GreatestSubsequentialSum

=={{header|Perl}}==

O(n) running-sum method:

 

sub max_sub(\@) {

 

print "seq: @a\nmax: [ @{[max_sub @a]} ]\n";

{{out}}

<pre>

 

Naive and potentionally very slow method:

 

my @a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);

}

 

 

=={{header|Phix}}==

{{Trans|Euphoria}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">maxSubseq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span> <span style="color: #000000;">maxSubseq</span><span style="color: #0000FF;">({})</span>

<span style="color: #0000FF;">?</span> <span style="color: #000000;">maxSubseq</span><span style="color: #0000FF;">({-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">})</span>

{{out}}

<pre>

=={{header|PHP}}==

 

<?php

print_array(max_sum_seq(array(4, -10, 3)));

?>

{{out}} in browser:

0 15 3 -9 12

(empty)

4

 

=={{header|Picat}}==

===Iterative===

First build a map with all the combinations then pick the one with greatest sum.

greatest_subsequential_sum_it(A) = Seq =>

P = allcomb(A),

allcomb(A) = Comb =>

Len = A.length,

 

===Constraint modelling===

(This was inspired by a MiniZinc model created by Claudio Cesar de Sá.)

greatest_subsequential_sum_cp(A) = Seq =>

N = A.length,

else

Seq = []

 

===Test===

 

go =>

end,

 

 

{{out}}

 

=={{header|PicoLisp}}==

(mapcon '((L) (maplist reverse (reverse L)))

{{out}}

<pre>-> (3 5 6 -2 -1 4)</pre>

 

=={{header|PL/I}}==

ss: Proc Options(Main);

/* REXX ***************************************************************

Put Edit('Sum:',maxSum)(Skip,a,f(5));

End;

{{out}}

<pre>

 

=={{header|Potion}}==

# Find discrete integral

integral = (0)

gss((-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))

gss((-1, -2, -3, -4, -5))

 

<pre>

CHR is a programming language created by '''Professor Thom Frühwirth'''.<br>

Works with SWI-Prolog and module CHR written by '''Tom Schrijvers''' and '''Jan Wielemaker'''.

 

:- chr_constraint

 

memoseq(DC, LC, TTC), gss(_D, _L, TT) <=> TTC > TT |

{{out}}

<pre> ?- greatest_subsequence.

===Brute Force===

Works with [https://rosettacode.org/wiki/GNU_Prolog GNU Prolog].

 

maxsubseq(List, Sub, Sum) :-

max_list(Sums, Sum),

nth(N, Sums, Sum),

{{out}}

<pre>| ?- maxsubseq([-1,-2,3,5,6,-2,-1,4,-4,2,-1], Sub, Sum).

 

=={{header|PureBasic}}==

Define s$, a, b, p1, p2, sum, max, dm=(?EndOfMyData-?MyData)

Dim Seq.i(dm/SizeOf(Integer))

Data.i -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1

EndOfMyData:

 

=={{header|Python}}==

===Imperative===

Naive, inefficient but really simple solution which tests all possible subsequences, as in a few of the other examples:

return max((seq[begin:end] for begin in xrange(len(seq)+1)

for end in xrange(begin, len(seq)+1)),

 

Classic linear-time constant-space solution based on algorithm from "Programming Pearls" book.

"""Return maximum sum."""

maxsofar, maxendinghere = 0, 0

maxendinghere = max(maxendinghere + x, 0)

maxsofar = max(maxsofar, maxendinghere)

Adapt the above-mentioned solution to return maximizing subsequence. See http://www.java-tips.org/java-se-tips/java.lang/finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-app.html

start, end, sum_start = -1, -1, -1

maxsum_, sum_ = 0, 0

assert maxsum_ == maxsum(sequence)

assert maxsum_ == sum(sequence[start + 1:end + 1])

Modify ``maxsumseq()`` to allow any iterable not just sequences.

maxseq = seq = []

start, end, sum_start = -1, -1, -1

sum_start = i

assert maxsum_ == sum(maxseq[:end - start])

Elementary tests:

assert f([]) == []

assert f([-1]) == []

assert f([-1, 2, -1, 3]) == [2, -1, 3]

assert f([-1, 2, -1, 3, -1]) == [2, -1, 3]

 

===Functional===

{{Trans|Haskell}}

{{Works with|Python|3.7}}

 

from functools import (reduce)

[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]

)

{{Out}}

<pre>(15, [3, 5, 6, -2, -1, 4])</pre>

 

=={{header|R}}==

cumulative <- cumsum(x)

min.cumulative.so.far <- Reduce(min, cumulative, accumulate=TRUE)

begin <- which.min(c(0, cumulative[1:end]))

if (end >= begin) x[begin:end] else x[c()]

{{out}}

 

=={{header|Racket}}==

Linear time version, returns the maximum subsequence and its sum.

(define (max-subseq l)

(define-values (_ result _1 max-sum)

(values (cons i seq) max-seq (+ sum i) max-sum)])))

(values (reverse result) max-sum))

For example:

> (max-subseq '(-1 -2 3 5 6 -2 -1 4 -4 2 -1))

'(3 5 6 -2 -1 4)

15

 

=={{header|Raku}}==

{{works with|Rakudo|2016.12}}

 

my ($start, $end, $sum, $maxsum) = -1, -1, 0, 0;

for @a.kv -> $i, $x {

}

return @a[$start ^.. $end];

 

Another solution, not translated from any other language:

The empty sequence is used to initialize $max-subset, which fulfils the "all negative" requirement of the problem.

 

 

my $max-subset = ();

max-subseq( -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ).say;

max-subseq( -2, -2, -1, 3, 5, 6, -1, 4, -4, 2, -1 ).say;

 

{{out}}

 

=={{header|Raven}}==

 

1 31 shl as $max

#dup "$seq[%d]\n" print

$seq swap get "%d," print

{{out}}

<pre>Sum: 3,5,6,-2,-1,4 = 15</pre>

===shortest greatest subsequential sum===

This REXX version will find the &nbsp; sum &nbsp; of the &nbsp; ''shortest greatest continuous subsequence''.

parse arg @; w= words(@); p= w + 1 /*get arg list; number words in list. */

say 'words='w " list="@ /*show number words & LIST to terminal,*/

say

$= subword(@,p,L); if $=='' then $= "[NULL]" /*Englishize the null (value). */

{{out|output|text=&nbsp; when the following was used for the list: &nbsp; &nbsp; <tt> -1 &nbsp; -2 &nbsp; 3 &nbsp; 5 &nbsp; 6 &nbsp; -2 &nbsp; -1 &nbsp; 4 &nbsp; -4 &nbsp; 2 &nbsp; -1 </tt>}}

<pre>

===longest greatest subsequential sum===

This REXX version will find the &nbsp; sum &nbsp; of the &nbsp; ''longest greatest continuous subsequence''.

parse arg @; w= words(@); p= w + 1 /*get arg list; number words in list. */

say 'words='w " list="@ /*show number words & LIST to terminal.*/

say

$= subword(@,p,L); if $=='' then $= "[NULL]" /*Englishize the null (value). */

{{out|output|text=&nbsp; when the following was used for the list: &nbsp; &nbsp; <tt> 1 &nbsp; 2 &nbsp; 3 &nbsp; 4 &nbsp; -777 &nbsp; 1 &nbsp; 2 &nbsp; 3 &nbsp; 4 &nbsp; 0 &nbsp; 0 </tt>}}

<pre>

 

===Version 3 (translated from Pascal)===

* 09.08.2012 Walter Pachl translated Pascal algorithm to Rexx

**********************************************************************/

Say ol

Say 'Sum:' maxSum

{{out}}

<pre>

 

=={{header|Ring}}==

# Project : Greatest subsequential sum

 

conv = left(conv, len(conv) - 2) + "]"

return conv

Output:

<pre>

===Brute Force:===

Answer is stored in "slice". It is very slow O(n**3)

max, slice = 0, []

arr.each_index do |i|

end

[max, slice]

'''Test:'''

[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],

[-1, -2, -3, -4, -5],

puts "\nInput seq: #{input}"

puts " Max sum: %d\n Subseq: %s" % subarray_sum(input)

{{out}}

<pre>

A better answer would run in O(n) instead of O(n**2) using numerical properties to remove the need for the inner loop.

 

# in the iteration if starting a new chain is

# better than your current score with this element

end

return max, arr[first..last]

The test result is the same above.

 

=={{header|Run BASIC}}==

max = -999

for i = 1 to 11

print word$(seq$,i,",");",";

next i

{{out}}

<pre>Sum: 3, 5, 6, -2, -1, 4, = 15</pre>

=={{header|Rust}}==

Naive brute force

let nums = [1,2,39,34,20, -20, -16, 35, 0];

 

 

println!("Max subsequence sum: {} for {:?}", max, &nums[boundaries]);;

{{out}}

<pre>Max subsequence sum: 96 for [1, 2, 39, 34, 20]</pre>

 

The last solution keeps to linear time by increasing complexity slightly.

case (el, acc) if acc.sum + el < 0 => Nil

case (el, acc) => el :: acc

case (el, (acc, ss)) => (acc + el, el :: ss)

} max Ordering.by((t: (N, List[N])) => (t._1, t._2.length)) _2

 

=={{header|Scheme}}==

(let loop

((_sum 0) (_seq (list)) (maxsum 0) (maxseq (list)) (l in))

(loop sum seq sum seq (cdr l))

(loop sum seq maxsum maxseq (cdr l)))

 

This returns a cons of the maximum sum and (one of) the maximum subsequence(s).

 

=={{header|Seed7}}==

const func array integer: maxSubseq (in array integer: sequence) is func

end for;

writeln;

{{out}}

<pre>

=={{header|Sidef}}==

{{trans|Raku}}

var (start, end, sum, maxsum) = (-1, -1, 0, 0);

a.each_kv { |i, x|

say maxsubseq(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1);

say maxsubseq(-2, -2, -1, 3, 5, 6, -1, 4, -4, 2, -1);

 

{{out}}

This is not a particularly efficient solution, but it gets the job done.

 

/*

This is a code implementation for finding one or more contiguous subsequences in a general sequence with the maximum sum of its elements.

select greatest_subsequential_sum('1,-1,+1', ',') from dual;

 

 

{{out}}

 

=={{header|Standard ML}}==

fun loop (_, _, maxsum, maxseq) [] = (maxsum, rev maxseq)

| loop (sum, seq, maxsum, maxseq) (x::xs) = let

end;

 

This returns a pair of the maximum sum and (one of) the maximum subsequence(s).

 

=={{header|Swift}}==

{{trans|C}}

var maxSum = 0, thisSum = 0, i = 0

var start = 0, end = -1

let (start, end, maxSum) = maxSubseq(sequence: a)

print("Max sum = \(maxSum)")

 

{{out}}

 

=={{header|Tcl}}==

set a {-1 -2 3 5 6 -2 -1 4 -4 2 -1}

 

puts [time {maxsumseq1 $a} 1000]

puts "maxsumseq2: [maxsumseq2 $a]"

{{out}}

<pre>sequence: -1 -2 3 5 6 -2 -1 4 -4 2 -1

=={{header|Ursala}}==

This example solves the problem by the naive algorithm of testing all possible subsequences.

#import int

 

#cast %zL

 

The general theory of operation is as follows.

* The <code>max_subsequence</code> function is a composition of three functions, one to generate the sequences, one to sum all of them, and one to pick out the one with the maximum sum.

 

=={{header|XPL0}}==

int Array, Size, Sum, Best, I, Lo, Hi, BLo, BHi;

 

CrLf(0);

Text(0, "Sum = "); IntOut(0, Best); CrLf(0);

 

{{out}}

=={{header|Wren}}==

{{trans|Go}}

var best = 0

var start = 0

System.print("Sub seq: %(subSeq)")

System.print("Sum: %(sum)\n")

 

{{out}}

=={{header|zkl}}==

{{trans|F#}}

s.reduce(fcn([(sum, seq, maxsum, maxseq)], x){

sum=sum+x; seq=T(x).extend(seq);

},

T(0,T,0,T))[3].reverse(); // -->maxseq.reverse()

println(s.sum()," : ",s);

 

s:=maxsubseq(T(-1,-2)); println(s.sum()," : ",s);

 

{{out}}

<pre>

=={{header|ZX Spectrum Basic}}==

{{trans|BBC_BASIC}}

20 DATA 11,-1,-2,3,5,6,-2,-1,4,-4,2,-1

30 DATA 5,-1,-2,-3,-4,-5

260 NEXT i

270 PRINT "]"