Greatest subsequential sum: Difference between revisions
m
→{{header|EasyLang}}
m (→Functional) |
|||
(42 intermediate revisions by 23 users not shown) | |||
Line 8:
An empty subsequence is considered to have the sum of '''0'''; thus if all elements are negative, the result must be the empty sequence.
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F maxsumseq(sequence)
V (start, end, sum_start) = (-1, -1, -1)
V (maxsum_, sum_) = (0, 0)
L(x) sequence
sum_ += x
I maxsum_ < sum_
maxsum_ = sum_
(start, end) = (sum_start, L.index)
E I sum_ < 0
sum_ = 0
sum_start = L.index
assert(maxsum_ == sum(sequence[start + 1 .. end]))
R sequence[start + 1 .. end]
print(maxsumseq([-1, 2, -1]))
print(maxsumseq([-1, 2, -1, 3, -1]))
print(maxsumseq([-1, 1, 2, -5, -6]))
print(maxsumseq([-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]))</syntaxhighlight>
{{out}}
<pre>
[2]
[2, -1, 3]
[1, 2]
[3, 5, 6, -2, -1, 4]
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintArray(INT ARRAY a INT first,last)
INT i
Put('[)
FOR i=first TO last
DO
IF i>first THEN Put(' ) FI
PrintI(a(i))
OD
Put(']) PutE()
RETURN
PROC Process(INT ARRAY a INT size)
INT i,j,beg,end
INT sum,best
beg=0 end=-1 best=0
FOR i=0 TO size-1
DO
sum=0
FOR j=i TO size-1
DO
sum==+a(j)
IF sum>best THEN
best=sum
beg=i
end=j
FI
OD
OD
Print("Seq=") PrintArray(a,0,size-1)
PrintF("Max sum=%i %ESubseq=",best)
PrintArray(a,beg,end) PutE()
RETURN
PROC Main()
INT ARRAY
a(11)=[1 2 3 4 5 65528 65527 65516 40 25 65531],
b(11)=[65535 65534 3 5 6 65534 65535 4 65532 2 65535],
c(5)=[65535 65534 65533 65532 65531],
d(0)=[]
Process(a,11)
Process(b,11)
Process(c,5)
Process(d,0)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Greatest_subsequential_sum.png Screenshot from Atari 8-bit computer]
<pre>
Seq=[1 2 3 4 5 -8 -9 -20 40 25 -5]
Max sum=65
Subseq=[40 25]
Seq=[-1 -2 3 5 6 -2 -1 4 -4 2 -1]
Max sum=15
Subseq=[3 5 6 -2 -1 4]
Seq=[-1 -2 -3 -4 -5]
Max sum=0
Subseq=[]
Seq=[]
Max sum=0
Subseq=[]
</pre>
=={{header|Ada}}==
<
procedure Max_Subarray is
Line 47 ⟶ 146:
when Empty_Error =>
Put_Line("Array being analyzed has no elements.");
end Max_Subarray;</
=={{header|Aime}}==
<syntaxhighlight lang="aime">gsss(list l, integer &start, &end, &maxsum)
{
integer e, f, i, sum;
end = f = maxsum = start = sum = 0;
for (i, e in l) {
sum += e;
if (sum < 0) {
sum = 0;
f = i + 1;
} elif (maxsum < sum) {
maxsum = sum;
end = i + 1;
start = f;
}
}
}
main(void)
{
integer start, end, sum;
list l;
l = list(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1);
gsss(l, start, end, sum);
o_("Max sum ", sum, "\n");
if (start < end) {
l.ocall(o_, 1, start, end - 1, " ");
o_newline();
}
0;
}</syntaxhighlight>
{{Out}}
<pre>Max sum 15
3 5 6 -2 -1 4</pre>
=={{header|ALGOL 68}}==
Line 54 ⟶ 191:
{{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);
Line 82 ⟶ 219:
OD
)</
{{out}}
<pre>
Line 91 ⟶ 228:
{{Trans|Haskell}}
Linear derivation of both sum and list, in a single fold:
<
on maxSubseq(xs)
script go
Line 179 ⟶ 316:
on Tuple(a, b)
{type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple</
{{Out}}
<pre>{15, {3, 5, 6, -2, -1, 4}}</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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"]
]</syntaxhighlight>
{{out}}
<pre> sequence: [1 2 3 4 5 -8 -9 -20 40 25 -5]
max sum: 65
subsequence: [40 25]
sequence: [-1 -2 3 5 6 -2 -1 4 -4 2 -1]
max sum: 15
subsequence: [3 5 6 -2 -1 4]
sequence: [-1 -2 -3 -4 -5]
max sum: 0
subsequence: []
sequence: []
max sum: 0
subsequence: [] </pre>
=={{header|ATS}}==
<syntaxhighlight lang="ats">
(*
** This one is
Line 256 ⟶ 450:
//
} (* end of [main0] *)
</syntaxhighlight>
{{out}}
<pre>
Line 265 ⟶ 459:
=={{header|AutoHotkey}}==
classic algorithm:
<
max := sum := start := 0
Loop Parse, seq, `,
Line 275 ⟶ 469:
Loop Parse, seq, `,
s .= A_Index > a && A_Index <= b ? A_LoopField "," : ""
MsgBox % "Max = " max "`n[" SubStr(s,1,-1) "]"</
=={{header|AutoIt}}==
<syntaxhighlight lang="autoit">
Local $iArray[11] = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
GREAT_SUB($iArray)
Line 315 ⟶ 509:
ConsoleWrite("]" & @CRLF & "!>SUM of subsequence: " & $iSUM & @CRLF)
EndFunc ;==>GREAT_SUB
</syntaxhighlight>
{{out}}
Line 330 ⟶ 524:
=={{header|AWK}}==
{{trans|Common Lisp}}
<
# Sets subseq[1] to subseq[n] and returns n. Also sets subseq["sum"].
# An empty subsequence has sum 0.
Line 357 ⟶ 551:
subseq["sum"] = b
return bn
}</
Demonstration: <
function join(ary, len, i, s) {
s = "["
Line 384 ⟶ 578:
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}}
Line 395 ⟶ 589:
=={{header|BBC BASIC}}==
<
PRINT FNshowarray(A%()) " -> " FNmaxsubsequence(A%())
DIM B%(10) : B%() = -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1
Line 430 ⟶ 624:
a$ += STR$(a%(i%)) + ", "
NEXT
= LEFT$(LEFT$(a$)) + "]"</
{{out}}
<pre>
Line 438 ⟶ 632:
</pre>
=={{header|Bracmat}}==
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
Line 524 ⟶ 659:
| !seq
)
</syntaxhighlight>
<pre>3 5 6 -2 -1 4</pre>
=={{header|C}}==
<
typedef struct Range {
Line 576 ⟶ 711:
return 0;
}</
{{out}}
<pre>Max sum = 15
3 5 6 -2 -1 4 </pre>
=={{header|C sharp|C#}}==
'''The challange'''
<syntaxhighlight lang="csharp">using System;
namespace Tests_With_Framework_4
{
class Program
{
static void Main(string[] args)
{
int[] integers = { -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 }; int length = integers.Length;
int maxsum, beginmax, endmax, sum; maxsum = beginmax = sum = 0; endmax = -1;
for (int i = 0; i < length; i++)
{
sum = 0;
for (int k = i; k < length; k++)
{
sum += integers[k];
if (sum > maxsum)
{
maxsum = sum;
beginmax = i;
endmax = k;
}
}
}
for (int i = beginmax; i <= endmax; i++)
Console.WriteLine(integers[i]);
Console.ReadKey();
}
}
}</syntaxhighlight>
=={{header|C++}}==
<
#include <iterator> // for std::iterator_traits
#include <iostream> // for std::cout
Line 670 ⟶ 841:
return 0;
}</
=={{header|Clojure}}==
{{trans|Haskell}}
Naive algorithm:
<
(->> (take-while seq (iterate rest coll)) ; tails
(mapcat #(reductions conj [] %)) ; inits
(apply max-key #(reduce + %)))) ; max sum</
{{out}}
<
[3 5 6 -2 -1 4]</
=={{header|CoffeeScript}}==
<
max_sum_seq = (sequence) ->
# This runs in linear time.
Line 740 ⟶ 875:
console.log max_sum_seq [-1]
console.log max_sum_seq [4, -10, 3]
</syntaxhighlight>
=={{header|Common Lisp}}==
Line 748 ⟶ 883:
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
Line 766 ⟶ 901:
(sum sum (- sum (first sublist))))
((or (endp sublist) (eql sum best-sum))
(values best-sum sublist start (1+ end)))))))</
For example,
Line 786 ⟶ 921:
{{trans|PicoLisp}}
<
(loop for subsequence in (mapcon (lambda (x) (maplist #'reverse (reverse x))) seq)
for sum = (reduce #'+ subsequence :initial-value 0)
Line 792 ⟶ 927:
maximizing sum into max
if (= sum max) do (setf max-subsequence subsequence)
finally (return max-subsequence))))</
=={{header|Component Pascal}}==
Works with BlackBox Component Builder
<syntaxhighlight lang="oberon2">
MODULE OvctGreatestSubsequentialSum;
IMPORT StdLog, Strings, Args;
PROCEDURE Gss(iseq: ARRAY OF INTEGER;OUT start, end, maxsum: INTEGER);
VAR
i,j,sum: INTEGER;
BEGIN
i := 0; maxsum := 0; start := 0; end := -1;
WHILE i < LEN(iseq) - 1 DO
sum := 0; j := i;
WHILE j < LEN(iseq) -1 DO
INC(sum ,iseq[j]);
IF sum > maxsum THEN
maxsum := sum;
start := i;
end := j
END;
INC(j);
END;
INC(i)
END
END Gss;
PROCEDURE Do*;
VAR
p: Args.Params;
iseq: POINTER TO ARRAY OF INTEGER;
i, res, start, end, sum: INTEGER;
BEGIN
Args.Get(p); (* Get Params *)
NEW(iseq,p.argc);
(* Transform params to INTEGERs *)
FOR i := 0 TO p.argc - 1 DO
Strings.StringToInt(p.args[i],iseq[i],res)
END;
Gss(iseq,start,end,sum);
StdLog.String("[");
FOR i := start TO end DO
StdLog.Int(iseq[i]);
IF i < end THEN StdLog.String(",") END
END;
StdLog.String("]=");StdLog.Int(sum);StdLog.Ln;
END Do;
END OvctGreatestSubsequentialSum.
</syntaxhighlight>
Execute: <br/>
<pre>
[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -2 3 5 6 -2 -1 4 -4 2 -2 ~
[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -5 -3 ~
</pre>
{{out}}
<pre>
[ 3, 5, 6, -2, -1, 4]= 15
[]= 0
</pre>
=={{header|Crystal}}==
===Brute Force:===
{{trans|Ruby}}
Answer is stored in "slice". It is very slow O(n**3)
<syntaxhighlight lang="ruby">def subarray_sum(arr)
max, slice = 0, [] of Int32
arr.each_index do |i|
(i...arr.size).each do |j|
sum = arr[i..j].sum
max, slice = sum, arr[i..j] if sum > max
end
end
[max, slice]
end</syntaxhighlight>
===Linear Time Version:===
{{trans|Ruby}}
A better answer would run in O(n) instead of O(n**2) using numerical properties to remove the need for the inner loop.
<syntaxhighlight lang="ruby"># the trick is that at any point
# in the iteration if starting a new chain is
# better than your current score with this element
# added to it, then do so.
# the interesting part is proving the math behind it
def subarray_sum(arr)
curr = max = 0
first, last, curr_first = arr.size, 0, 0
arr.each_with_index do |e, i|
curr += e
e > curr && (curr = e; curr_first = i)
curr > max && (max = curr; first = curr_first; last = i)
end
return max, arr[first..last]
end</syntaxhighlight>
'''Test:'''
<syntaxhighlight lang="ruby">[ [1, 2, 3, 4, 5, -8, -9, -20, 40, 25, -5],
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],
[-1, -2, -3, -4, -5],
[] of Int32
].each do |input|
puts "\nInput seq: #{input}"
puts " Max sum: %d\n Subseq: %s" % subarray_sum(input)
end</syntaxhighlight>
{{out}}
<pre>
Input seq: [1, 2, 3, 4, 5, -8, -9, -20, 40, 25, -5]
Max sum: 65
Subseq: [40, 25]
Input seq: [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
Max sum: 15
Subseq: [3, 5, 6, -2, -1, 4]
Input seq: [-1, -2, -3, -4, -5]
Max sum: 0
Subseq: []
Input seq: []
Max sum: 0
Subseq: []
</pre>
=={{header|D}}==
{{trans|Python}}
<
inout(T[]) maxSubseq(T)(inout T[] sequence) pure nothrow @nogc {
Line 825 ⟶ 1,083:
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]
Line 836 ⟶ 1,094:
and max can't be used as the maximumBy functions
(for the concatMap a map.join is enough).
<
mixin template InitsTails(T) {
Line 869 ⟶ 1,127:
[-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].
=={{header|E}}==
This implementation tests every combination, but it first examines the sequence to reduce the number of combinations tried: We need not consider beginning the subsequence at any point which is not the beginning, or a change from negative to positive. We need not consider ending the subsequence at any point which is not the end, or a change from positive to negative. (Zero is moot and treated as negative.)
This algorithm is therefore <math>O(nm^2)</math> where <math>n</math> is the size of the sequence and <math>m</math> is the number of sign changes in the sequence. [[User:Kevin Reid|I]] think it could be improved to <math>O(n + m^2)</math> by recording the positive and negative intervals' sums during the initial pass and accumulating the sum of those sums in the inner for loop.
<code>maxSubseq</code> returns both the maximum sum found, and the interval of indexes which produces it.
<syntaxhighlight lang="e">pragma.enable("accumulator")
def maxSubseq(seq) {
def size := seq.size()
# Collect all intervals of indexes whose values are positive
def intervals := {
var intervals := []
var first := 0
while (first < size) {
var next := first
def seeing := seq[first] > 0
while (next < size && (seq[next] > 0) == seeing) {
next += 1
}
if (seeing) { # record every positive interval
intervals with= first..!next
}
first := next
}
intervals
}
# For recording the best result found
var maxValue := 0
var maxInterval := 0..!0
# Try all subsequences beginning and ending with such intervals.
for firstIntervalIx => firstInterval in intervals {
for lastInterval in intervals(firstIntervalIx) {
def interval :=
(firstInterval.getOptStart())..!(lastInterval.getOptBound())
def value :=
accum 0 for i in interval { _ + seq[i] }
if (value > maxValue) {
maxValue := value
maxInterval := interval
}
}
}
return ["value" => maxValue,
"indexes" => maxInterval]
}</syntaxhighlight>
<syntaxhighlight lang="e">def seq := [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
def [=> value, => indexes] := maxSubseq(seq)
println(`$\
Sequence: $seq
Maximum subsequence sum: $value
Indexes: ${indexes.getOptStart()}..${indexes.getOptBound().previous()}
Subsequence: ${seq(indexes.getOptStart(), indexes.getOptBound())}
`)</syntaxhighlight>
=={{header|EasyLang}}==
{{trans|C}}
<syntaxhighlight>
proc max_subseq . seq[] start stop maxsum .
maxsum = 0
i = 1
start = 1
stop = 0
for j to len seq[]
sum += seq[j]
if sum < 0
i = j + 1
sum = 0
elif sum > maxsum
start = i
stop = j
maxsum = sum
.
.
.
a[] = [ -1 -2 3 5 6 -2 -1 4 -4 2 -1 ]
max_subseq a[] a b sum
print "Max sum = " & sum
for i = a to b
write a[i] & " "
.
</syntaxhighlight>
{{out}}
<pre>
Max sum = 15
3 5 6 -2 -1 4
</pre>
=={{header|EchoLisp}}==
<
(lib 'struct)
(struct result (score starter))
Line 908 ⟶ 1,262:
(max-seq L)
→ (15 (3 5 6 -2 -1 4))
</syntaxhighlight>
=={{header|Elixir}}==
{{trans|Ruby}}
===Linear Time Version:===
<syntaxhighlight lang="elixir">defmodule Greatest do
def subseq_sum(list) do
list_i = Enum.with_index(list)
acc = {0, 0, length(list), 0, 0}
{_,max,first,last,_} = Enum.reduce(list_i, acc, fn {elm,i},{curr,max,first,last,curr_first} ->
if curr < 0 do
if elm > max, do: {elm, elm, i, i, curr_first},
else: {elm, max, first, last, curr_first}
else
cur2 = curr + elm
if cur2 > max, do: {cur2, cur2, curr_first, i, curr_first},
else: {cur2, max, first, last, curr_first}
end
end)
{max, Enum.slice(list, first..last)}
end
end</syntaxhighlight>
Output is the same above.
===Brute Force:===
<
def subseq_sum(list) do
limit = length(list) - 1
Line 923 ⟶ 1,297:
end)
end
end</
'''Test:'''
<
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],
[-1, -2, -3, -4, -5],
Line 934 ⟶ 1,308:
{max, subseq} = Greatest.subseq_sum(input)
IO.puts " Max sum: #{max}\n Subseq: #{inspect subseq}"
end)</
{{out}}
Line 954 ⟶ 1,328:
Subseq: []
</pre>
=={{header|ERRE}}==
<syntaxhighlight lang="text">
PROGRAM MAX_SUM
Line 1,044 ⟶ 1,398:
!$ERASE P%
END PROGRAM
</syntaxhighlight>
=={{header|Euler Math Toolbox}}==
Line 1,050 ⟶ 1,404:
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).
<syntaxhighlight lang="euler math toolbox">
>function %maxsubs (v,n) ...
$if n==1 then
Line 1,074 ⟶ 1,428:
>maxsubs([-1, -2, -3, -4, -5])
Empty matrix of size 1x0
</syntaxhighlight>
Here is a brute force method producing and testing all sums. The runtime is O(n^3).
<syntaxhighlight lang="euler math toolbox">
>function maxsubsbrute (v) ...
$ n=cols(v);
Line 1,098 ⟶ 1,452:
>maxsubsbrute([-1, -2, -3, -4, -5])
Empty matrix of size 1x0
</syntaxhighlight>
To see, if everything works, the following tests on 10 million random sequences.
<syntaxhighlight lang="euler math toolbox">
>function test ...
$ loop 1 to 10000000
Line 1,111 ⟶ 1,465:
$ endfunction
>test
</syntaxhighlight>
=={{header|Euphoria}}==
<
integer sum, maxsum, first, last
maxsum = 0
Line 1,196 ⟶ 1,489:
? maxSubseq({-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1})
? maxSubseq({})
? maxSubseq({-1, -5, -3})</
{{out}}
Line 1,202 ⟶ 1,495:
{}
{}</pre>
=={{header|F_Sharp|F#}}==
<
let (_, _, maxsum, maxseq) =
List.fold (fun (sum, seq, maxsum, maxseq) x ->
Line 1,215 ⟶ 1,507:
List.rev maxseq
printfn "%A" (maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1])</
{{out}}
<pre>[3; 5; 6; -2; -1; 4]</pre>
=={{header|Factor}}==
<
:: max-with-index ( elt0 ind0 elt1 ind1 -- elt ind )
Line 1,228 ⟶ 1,520:
: 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 ;</
<
{ 3 5 6 -2 -1 4 }
15</
=={{header|Forth}}==
<
variable best-sum
Line 1,256 ⟶ 1,548:
create test -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1 ,
create test2 -1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , 99 ,</
{{out}}
<
test2 11 max-sub .array [3 5 6 -2 -1 4 -4 2 99 ] = 112 ok</
=={{header|Fortran}}==
{{works with|Fortran|95 and later}}
<
implicit none
Line 1,278 ⟶ 1,570:
print *, a(m(1):m(2))
end program MaxSubSeq</
=={{header|FreeBASIC}}==
<
Dim As Integer seq(10) = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1}
Line 1,316 ⟶ 1,608:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,326 ⟶ 1,618:
=={{header|Go}}==
<
import "fmt"
Line 1,361 ⟶ 1,653:
fmt.Println("Sum: ", sum, "\n")
}
}</
{{out}}
<pre>
Line 1,383 ⟶ 1,675:
=={{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)
Line 1,392 ⟶ 1,684:
maxsubseq = maximumBy (comparing sum) . subseqs
main = print $ maxsubseq [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]</
Secondly, the linear time constant space approach:
<
maxSubseq =
let go x ((h1, h2), sofar) =
in snd . foldr go ((0, []), (0, []))
main :: IO ()
main = print $ maxSubseq [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]</
{{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
Line 1,428 ⟶ 1,719:
}
return L[(\maxglobalI)[1]:maxglobalI[2]] | [] # return sub-sequence or empty list
end</
=={{header|IS-BASIC}}==
<
110 RANDOMIZE
120 NUMERIC A(1 TO 15)
Line 1,452 ⟶ 1,743:
290 PRINT A(I);
300 NEXT
310 PRINT :PRINT "Sum:";MAXSUM</
=={{header|J}}==
<
AS =. 0,; <:/~@i.&.> #\y
MX =. (= >./) AS +/ . * y
y #~ {. MX#AS
)</
<tt>y</tt> is the input vector, an integer list.<br>
Line 1,469 ⟶ 1,760:
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:
<
3 5 6 _2 _1 4</
Note: if we just want the sum of the maximum subsequence,
and are not concerned with the subsequence itself, we can use:
<
Example use:
<
15</
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.
Line 1,500 ⟶ 1,791:
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;
Line 1,556 ⟶ 1,847:
return false;
}
}</
This one runs in linear time, and isn't generalized.
<
int sum = 0;
int maxsum = 0;
Line 1,570 ⟶ 1,861:
}
return maxsum;
}</
=={{header|JavaScript}}==
===Imperative===
Simple brute force approach.
<
var maxValue = 0;
var subsequence = [];
Line 1,599 ⟶ 1,890:
}
return result;
}</
===Functional===
{{Trans|Haskell}}
Linear approach, deriving both list and sum in a single accumulating fold.
<
// maxSubseq :: [Int] -> (Int, [Int])
Line 1,662 ⟶ 1,953:
// MAIN ---
return main();
})();</
{{Out}}
<pre>[3,5,6,-2,-1,4] -> 15</pre>
Line 1,670 ⟶ 1,961:
This is the same linear-time algorithm as used in the [[#Ruby]] subsection on this page.
<
. as $arr
| reduce range(0; length) as $i
Line 1,680 ⟶ 1,971:
else .
end)
| [ .max, $arr[ .first : (1 + .last)] ];</
'''Example''':
<
{{out}}
<
[65,[40,25]]</
=={{header|Jsish}}==
From Javascript entry.
<syntaxhighlight lang="javascript">/* Greatest Subsequential Sum, in Jsish */
function sumValues(arr) {
var result = 0;
for (var i = 0, len = arr.length; i < len; i++) result += arr[i];
return result;
}
function greatestSubsequentialSum(population:array):array {
var maxValue = (population[0]) ? population[0] : 0;
var subsequence = [], greatest = [];
for (var i = 0, len = population.length; i < len; i++) {
for (var j = i; j < len; j++) {
subsequence = population.slice(i, j);
var value = sumValues(subsequence);
if (value > maxValue) {
maxValue = value;
greatest = subsequence;
};
}
}
return [maxValue, greatest];
}
if (Interp.conf('unitTest')) {
var gss = [-1,-2,3,5,6,-2,-1,4,-4,2,-1];
; gss;
; greatestSubsequentialSum(gss);
}
/*
=!EXPECTSTART!=
gss ==> [ -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ]
greatestSubsequentialSum(gss) ==> [ 15, [ 3, 5, 6, -2, -1, 4 ] ]
=!EXPECTEND!=
*/</syntaxhighlight>
{{out}}
<pre>prompt$ jsish --U greatestSubsequentialSum.jsi
gss ==> [ -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1 ]
greatestSubsequentialSum(gss) ==> [ 15, [ 3, 5, 6, -2, -1, 4 ] ]</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<
smax = hmax = tmax = 0
for head in eachindex(arr), tail in head:length(arr)
Line 1,706 ⟶ 2,042:
s = sum(subseq)
println("Greatest subsequential sum of $arr:\n → $subseq with sum $s")</
{{out}}
Line 1,713 ⟶ 2,049:
=={{header|Kotlin}}==
<
fun gss(seq: IntArray): Triple<Int, Int, Int> {
Line 1,746 ⟶ 2,082:
else
println("Maximum subsequence is the empty sequence which has a sum of 0")
}</
{{out}}
Line 1,756 ⟶ 2,092:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
'Greatest_subsequential_sum
Line 1,809 ⟶ 2,145:
print
end sub
</
=={{header|Lua}}==
<
function maxsub(ary, idx)
local idx = idx or 1
Line 1,824 ⟶ 2,161:
for i = idx, last do ret[#ret+1] = ary[i] end
return ret
end</
=={{header|M4}}==
<
define(`setrange',`ifelse(`$3',`',$2,`define($1[$2],$3)`'setrange($1,
incr($2),shift(shift(shift($@))))')')
Line 1,842 ⟶ 2,179:
`define(`maxsum',sum)`'define(`xmax',x)`'define(`ymax',y)')')')
divert
for(`x',xmax,ymax,`get(`a',x) ')</
=={{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}]
MaximumSubsequence[{}]</
gives back:
<pre>{3,5,6,-2,-1,4}
Line 1,871 ⟶ 2,208:
=={{header|Mathprog}}==
see [[wp:Special_ordered_set]]. Lmin specifies the minimum length of the required subsequence, and Lmax the maximum.
<syntaxhighlight lang="text">
/*Special ordered set of type N
Line 1,908 ⟶ 2,245:
end;
</syntaxhighlight>
produces:
<syntaxhighlight lang="text">
GLPSOL: GLPK LP/MIP Solver, v4.47
Parameter(s) specified in the command line:
Line 1,952 ⟶ 2,289:
Model has been successfully processed
</syntaxhighlight>
=={{header|MATLAB}} / {{header|Octave}}==
<
% Greatest subsequential sum
a =[0;a(:);0]';
Line 1,969 ⟶ 2,306:
end;
GS = a(ix1(K)+1:ix2(K));
</syntaxhighlight>
Usage:
Line 1,980 ⟶ 2,317:
=={{header|NetRexx}}==
<
* 10.08.2012 Walter Pachl Pascal algorithm -> Rexx -> NetRexx
**********************************************************************/
Line 2,011 ⟶ 2,348:
Say ol
Say 'Sum:' maxSum
End</
Output: the same as for Rexx
=={{header|Nim}}==
<
var maxendinghere = 0
for x in s:
Line 2,021 ⟶ 2,358:
result = max(result, maxendinghere)
echo maxsum(@[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1])</
{{out}}
<pre>15</pre>
=={{header|Oberon-2}}==
Works with oo2c Version 2
<
MODULE GreatestSubsequentialSum;
IMPORT
Line 2,112 ⟶ 2,452:
END GreatestSubsequentialSum.
</syntaxhighlight>
Execute:<br/>
<pre>
Line 2,125 ⟶ 2,465:
=={{header|OCaml}}==
<
let rec loop sum seq maxsum maxseq = function
| [] -> maxsum, List.rev maxseq
Line 2,141 ⟶ 2,481:
let _ =
maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1]</
This returns a pair of the maximum sum and (one of) the maximum subsequence(s).
=={{header|Oz}}==
<
fun {MaxSubSeq Xs}
Line 2,169 ⟶ 2,509:
end
in
{Show {MaxSubSeq [~1 ~2 3 5 6 ~2 ~1 4 ~4 2 1]}}</
=={{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]));
Line 2,186 ⟶ 2,526:
);
at
};</
=={{header|Pascal}}==
<
var
Line 2,228 ⟶ 2,568:
writeln ('Sum:');
writeln (maxSum);
end.</
{{out}}
<pre>:> ./GreatestSubsequentialSum
Line 2,241 ⟶ 2,581:
=={{header|Perl}}==
O(n) running-sum method:
<
sub max_sub(\@) {
Line 2,261 ⟶ 2,601:
print "seq: @a\nmax: [ @{[max_sub @a]} ]\n";
print "seq: @b\nmax: [ @{[max_sub @b]} ]\n";</
{{out}}
<pre>
Line 2,271 ⟶ 2,611:
Naive and potentionally very slow method:
<
my @a = (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);
Line 2,289 ⟶ 2,629:
}
print "@maxsubarray\n";</
=={{header|Phix}}==
{{Trans|Euphoria}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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: #004080;">integer</span> <span style="color: #000000;">maxsum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">first</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sumsij</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">sumsij</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sumsij</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxsum</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">maxsum</span><span style="color: #0000FF;">,</span><span style="color: #000000;">first</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">sumsij</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">first</span><span style="color: #0000FF;">..</span><span style="color: #000000;">last</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</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;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">6</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</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;">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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,370 ⟶ 2,661:
=={{header|PHP}}==
<syntaxhighlight lang="php">
<?php
Line 2,409 ⟶ 2,700:
print_array(max_sum_seq(array(4, -10, 3)));
?>
</syntaxhighlight>
{{out}} in browser:
<syntaxhighlight lang="text">
0 15 3 -9 12
(empty)
4
</syntaxhighlight>
=={{header|Picat}}==
Here are two versions: one iterative and one using constraint modelling (constraint programming solver).
===Iterative===
First build a map with all the combinations then pick the one with greatest sum.
<syntaxhighlight lang="picat">greatest_subsequential_sum_it([]) = [] => true.
greatest_subsequential_sum_it(A) = Seq =>
P = allcomb(A),
Total = max([Tot : Tot=_T in P]),
Seq1 = [],
if Total > 0 then
[B,E] = P.get(Total),
Seq1 := [A[I] : I in B..E]
else
Seq1 := []
end,
Seq = Seq1.
allcomb(A) = Comb =>
Len = A.length,
Comb = new_map([(sum([A[I]:I in B..E])=([B,E])) : B in 1..Len, E in B..Len]).</syntaxhighlight>
===Constraint modelling===
(This was inspired by a MiniZinc model created by Claudio Cesar de Sá.)
<syntaxhighlight lang="picat">greatest_subsequential_sum_cp([]) = [] => true.
greatest_subsequential_sum_cp(A) = Seq =>
N = A.length,
% decision variables: start and end indices
Begin :: 1..N,
End :: 1..N,
% 1 if the number is in the selected sequence, 0 if not.
X = new_list(N),
X :: 0..1,
% Get the total sum (to be maximized)
TotalSum #= sum([X[I]*A[I] : I in 1..N]),
SizeWindow #= sum(X),
% Calculate the windows of the greatest subsequential sum
End #>= Begin,
End - Begin #= SizeWindow -1,
foreach(I in 1..N)
(Begin #=< I #/\ End #>= I) #<=> X[I] #= 1
end,
Vars = X ++ [Begin,End],
solve($[inout,updown,max(TotalSum)], Vars),
if TotalSum > 0 then
Seq = [A[I] : I in Begin..End]
else
Seq = []
end.</syntaxhighlight>
===Test===
<syntaxhighlight lang="picat">import cp.
go =>
LL = [[-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1],
[-1,-2, 3],
[-1,-2],
[0],
[],
[144, 5, -8, 7, 15],
[144, -145, -8, 7, 15],
[-144, 5, -8, 7, 15]
],
println("Iterative version:"),
foreach(L in LL)
printf("%w: ", L),
G = greatest_subsequential_sum_it(L),
println([gss=G, sum=sum(G)])
end,
nl,
println("Constraint model"),
foreach(L in LL)
printf("%w: ", L),
G = greatest_subsequential_sum_cp(L),
println([gss=G, sum=sum(G)])
end,
nl.</syntaxhighlight>
{{out}}
<pre>Iterative version:
[-1,-2,3,5,6,-2,-1,4,-4,2,-1]: [gss = [3,5,6,-2,-1,4],sum = 15]
[-1,-2,3]: [gss = [3],sum = 3]
[-1,-2]: [gss = [],sum = 0]
[0]: [gss = [],sum = 0]
[]: [gss = [],sum = 0]
[144,5,-8,7,15]: [gss = [144,5,-8,7,15],sum = 163]
[144,-145,-8,7,15]: [gss = [144],sum = 144]
[-144,5,-8,7,15]: [gss = [7,15],sum = 22]
Constraint model
[-1,-2,3,5,6,-2,-1,4,-4,2,-1]: [gss = [3,5,6,-2,-1,4],sum = 15]
[-1,-2,3]: [gss = [3],sum = 3]
[-1,-2]: [gss = [],sum = 0]
[0]: [gss = [],sum = 0]
[]: [gss = [],sum = 0]
[144,5,-8,7,15]: [gss = [144,5,-8,7,15],sum = 163]
[144,-145,-8,7,15]: [gss = [144],sum = 144]
[-144,5,-8,7,15]: [gss = [7,15],sum = 22]</pre>
=={{header|PicoLisp}}==
<
(mapcon '((L) (maplist reverse (reverse L)))
(-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )</
{{out}}
<pre>-> (3 5 6 -2 -1 4)</pre>
=={{header|PL/I}}==
<
ss: Proc Options(Main);
/* REXX ***************************************************************
Line 2,465 ⟶ 2,864:
Put Edit('Sum:',maxSum)(Skip,a,f(5));
End;
End;</
{{out}}
<pre>
Line 2,476 ⟶ 2,875:
=={{header|Potion}}==
<
# Find discrete integral
integral = (0)
Line 2,505 ⟶ 2,904:
gss((-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))
gss((-1, -2, -3, -4, -5))
gss((7,-6, -8, 5, -2, -6, 7, 4, 8, -9, -3, 2, 6, -4, -6))</
<pre>
Line 2,517 ⟶ 2,916:
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
Line 2,571 ⟶ 2,970:
memoseq(DC, LC, TTC), gss(_D, _L, TT) <=> TTC > TT |
gss(DC, LC, TTC).</
{{out}}
<pre> ?- greatest_subsequence.
Line 2,582 ⟶ 2,981:
===Brute Force===
Works with [https://rosettacode.org/wiki/GNU_Prolog GNU Prolog].
<
maxsubseq(List, Sub, Sum) :-
Line 2,589 ⟶ 2,988:
max_list(Sums, Sum),
nth(N, Sums, Sum),
nth(N, Subs, Sub).</
{{out}}
<pre>| ?- maxsubseq([-1,-2,3,5,6,-2,-1,4,-4,2,-1], Sub, Sum).
Line 2,600 ⟶ 2,999:
=={{header|PureBasic}}==
<
Define s$, a, b, p1, p2, sum, max, dm=(?EndOfMyData-?MyData)
Dim Seq.i(dm/SizeOf(Integer))
Line 2,634 ⟶ 3,033:
Data.i -1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1
EndOfMyData:
EndDataSection</
=={{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)),
key=sum)</
Classic linear-time constant-space solution based on algorithm from "Programming Pearls" book.
<
"""Return maximum sum."""
maxsofar, maxendinghere = 0, 0
Line 2,652 ⟶ 3,051:
maxendinghere = max(maxendinghere + x, 0)
maxsofar = max(maxsofar, maxendinghere)
return maxsofar</
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
Line 2,667 ⟶ 3,066:
assert maxsum_ == maxsum(sequence)
assert maxsum_ == sum(sequence[start + 1:end + 1])
return sequence[start + 1:end + 1]</
Modify ``maxsumseq()`` to allow any iterable not just sequences.
<
maxseq = seq = []
start, end, sum_start = -1, -1, -1
Line 2,682 ⟶ 3,081:
sum_start = i
assert maxsum_ == sum(maxseq[:end - start])
return maxseq[:end - start]</
Elementary tests:
<
assert f([]) == []
assert f([-1]) == []
Line 2,700 ⟶ 3,099:
assert f([-1, 2, -1, 3]) == [2, -1, 3]
assert f([-1, 2, -1, 3, -1]) == [2, -1, 3]
assert f([-1, 1, 2, -5, -6]) == [1,2]</
===Functional===
We can efficiently derive sum and sequence together, without mutation, using '''reduce''' to express a linear accumulation over a fold:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Greatest subsequential sum'''
from functools import (reduce)
# maxSubseq :: [Int] -> [Int] -> (Int, [Int])
def maxSubseq(xs):
'''Subsequence of xs with the maximum sum'''
def go(ab, x):
(m1, m2) = ab[0]
return (
return reduce(go, xs, ((0, []), (0, [])))[1]
# TEST -----------------------------------------------------------
print(
maxSubseq(
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
)
)</
{{Out}}
<pre>(15, [3, 5, 6, -2, -1, 4])</pre>
=={{header|Quackery}}==
<syntaxhighlight lang="Quackery"> [ stack ] is maxseq ( --> s )
[ stack ] is maxsum ( --> s )
[ [] maxseq put
0 maxsum put
dup dup size times
[ [] 0 rot
witheach
[ rot over join
unrot +
dup maxsum share >
if
[ dup maxsum replace
over maxseq replace ] ]
2drop behead drop dup ]
2drop
maxsum take
maxseq take ] is maxsubseqsum ( [ --> n [ )
' [ [ 1 2 3 4 5 -8 -9 -20 40 25 -5 ]
[ -1 -2 3 5 6 -2 -1 4 -4 2 -1 ]
[ -1 -2 -3 -4 -5 ]
[ ] ]
witheach
[ dup
say "Sequence: " echo cr
maxsubseqsum
say "Subsequence: " echo cr
say "Sum: " echo cr
cr ]</syntaxhighlight>
{{out}}
<pre>Sequence: [ 1 2 3 4 5 -8 -9 -20 40 25 -5 ]
Subsequence: [ 40 25 ]
Sum: 65
Sequence: [ -1 -2 3 5 6 -2 -1 4 -4 2 -1 ]
Subsequence: [ 3 5 6 -2 -1 4 ]
Sum: 15
Sequence: [ -1 -2 -3 -4 -5 ]
Subsequence: [ ]
Sum: 0
Sequence: [ ]
Subsequence: [ ]
Sum: 0
</pre>
=={{header|R}}==
<
cumulative <- cumsum(x)
min.cumulative.so.far <- Reduce(min, cumulative, accumulate=TRUE)
Line 2,732 ⟶ 3,189:
begin <- which.min(c(0, cumulative[1:end]))
if (end >= begin) x[begin:end] else x[c()]
}</
{{out}}
<
[1] 3 5 6 -2 -1 4</
=={{header|Racket}}==
Linear time version, returns the maximum subsequence and its sum.
<
(define (max-subseq l)
(define-values (_ result _1 max-sum)
Line 2,751 ⟶ 3,208:
(values (cons i seq) max-seq (+ sum i) max-sum)])))
(values (reverse result) max-sum))
</syntaxhighlight>
For example:
<syntaxhighlight lang="racket">
> (max-subseq '(-1 -2 3 5 6 -2 -1 4 -4 2 -1))
'(3 5 6 -2 -1 4)
15
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Python}}
{{works with|Rakudo|2016.12}}
<syntaxhighlight lang="raku" line>sub max-subseq (*@a) {
my ($start, $end, $sum, $maxsum) = -1, -1, 0, 0;
for @a.kv -> $i, $x {
$sum += $x;
if $maxsum < $sum {
($maxsum, $end) = $sum, $i;
}
elsif $sum < 0 {
($sum, $start) = 0, $i;
}
}
return @a[$start ^.. $end];
}</syntaxhighlight>
Another solution, not translated from any other language:
For each starting position, we calculate all the subsets starting at that position.
They are combined with the best subset ($max-subset) from previous loops, to form (@subsets).
The best of those @subsets is saved at the new $max-subset.
Consuming the array (.shift) allows us to skip tracking the starting point; it is always 0.
The empty sequence is used to initialize $max-subset, which fulfils the "all negative" requirement of the problem.
<syntaxhighlight lang="raku" line>sub max-subseq ( *@a ) {
my $max-subset = ();
while @a {
my @subsets = [\,] @a;
@subsets.push: $max-subset;
$max-subset = @subsets.max: { [+] .list };
@a.shift;
}
return $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;
max-subseq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).say;</syntaxhighlight>
{{out}}
<pre>
(3 5 6 -2 -1 4)
(3 5 6 -1 4)
()</pre>
=={{header|Raven}}==
<
1 31 shl as $max
Line 2,777 ⟶ 3,287:
#dup "$seq[%d]\n" print
$seq swap get "%d," print
$max $seq $j1 get "%d = %d\n" print</
{{out}}
<pre>Sum: 3,5,6,-2,-1,4 = 15</pre>
Line 2,784 ⟶ 3,294:
===shortest greatest subsequential sum===
This REXX version will find the sum of the ''shortest greatest continuous subsequence''.
<
parse arg @; w= words(@); p= w +
say 'words='w " list="@ /*show number words & LIST to terminal
L=0; sum=
do j=1 for w
do k=j to w;
do m=j+1 to k; s= s +
if (s==sum & _>L) | s>sum then do; sum= s;
end /*k*/ /* [↑] chose the longest greatest sum
end /*j*/
say
$= subword(@,
say 'sum='sum/1
<pre>
words=11 list=-1 -2 3 5 6 -2 -1 4 -4 2 -1
Line 2,804 ⟶ 3,314:
sum=15 sequence=3 5 6 -2 -1 4
</pre>
<pre>
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0
Line 2,813 ⟶ 3,323:
===longest greatest subsequential sum===
This REXX version will find the sum of the ''longest greatest continuous subsequence''.
<
parse arg @; w= words(@); p= w +
say 'words='w " list="@ /*show number words & LIST to terminal
L=0; sum=
do j=1 for w
do k=j to w;
if
end /*k*/ /* [↑] chose
end /*j*/
say
$= subword(@,
say 'sum='sum/1
<pre>
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0
Line 2,835 ⟶ 3,345:
===Version 3 (translated from Pascal)===
<
* 09.08.2012 Walter Pachl translated Pascal algorithm to Rexx
**********************************************************************/
Line 2,865 ⟶ 3,375:
Say ol
Say 'Sum:' maxSum
End</
{{out}}
<pre>
Line 2,876 ⟶ 3,386:
=={{header|Ring}}==
<
# Project : Greatest subsequential sum
Line 2,925 ⟶ 3,435:
conv = left(conv, len(conv) - 2) + "]"
return conv
</syntaxhighlight>
Output:
<pre>
Line 2,933 ⟶ 3,443:
[] - > 0
</pre>
=={{header|RPL}}==
{{works with|HP|48G}}
≪ DUP SIZE -> input size
≪ { }
'''CASE'''
size NOT '''THEN END''' <span style="color:grey">@ empty list case</span>
size 1 == '''THEN''' <span style="color:grey">@ singleton case</span>
'''IF''' input 1 GET 0 ≥ '''THEN''' DROP input '''END'''
'''END'''
input 0 < ΠLIST NOT '''THEN''' <span style="color:grey">@ for any list with at least 1 item > 0</span>
input ≪ MAX ≫ STREAM <span style="color:grey">@ initialize sum with maximum item</span>
+ LASTARG SWAP DROP
1 size 2 - '''FOR''' len
1 size len - '''FOR''' j
input j DUP len + SUB
DUP ∑LIST 3 PICK
'''IF''' OVER < '''THEN''' 4 ROLL 4 ROLL '''END'''
DROP2
'''NEXT NEXT'''
DROP
'''END'''
'''END'''
≫ ≫ '<span style="color:blue">BIGSUB</span>' STO
{ { -1 } { -1 2 -1 } { -1 2 -1 3 -1 } { -1 1 2 -5 -6 } { -1 -2 3 5 6 -2 -1 4 -4 2 -1 } }
1 ≪ <span style="color:blue">BIGSUB</span> ≫ DOLIST
{{out}}
<pre>
1: { { } { 2 } { 2 -1 3 } { 1 2 } { 3 5 6 -2 -1 4 } }
</pre>
===Using matrices===
{{trans|Fortran}}
{{works with|HP|49}}
≪ DUP SIZE → input size
≪ { }
'''CASE'''
size 1 == '''THEN''' <span style="color:grey">@ singleton case</span>
'''IF''' input 1 GET 0 ≥ '''THEN''' DROP input '''END'''
'''END'''
size '''THEN'''
DROP
size DUP ≪ → j k ≪ '''IF''' j k ≤ '''THEN''' input j k SUB 0 + ∑LIST '''ELSE''' 0 '''END''' ≫ ≫ LCXM
<span style="color:grey">@ forall(i=1:an,j=1:an) mix(i,j) = sum(a(i:j))</span>
OBJ→ ΠLIST →LIST DUP ≪ MAX ≫ STREAM POS <span style="color:grey">@ m = maxloc(mix)</span>
1 - size IDIV2 R→C (1,1) + input SWAP C→R SUB <span style="color:grey">@ print *, a(m(1):m(2))</span>
'''END'''
'''END'''
≫ ≫ '<span style="color:blue">BIGSUB</span>' STO
===Efficient solution===
Uses only basic RPL instructions for maximum compatibility.
{{trans|Euphoria}}
≪ DUP SIZE → s length
≪ <span style="color:red">{ }</span>
'''IF''' length '''THEN'''
<span style="color:red">0 (1 0)</span>
<span style="color:red">1</span> length '''FOR''' j
<span style="color:red">0</span>
j length '''FOR''' k
s k GET +
'''IF''' <span style="color:red">3</span> PICK OVER < '''THEN'''
ROT ROT DROP2
j k R→C OVER
'''END'''
'''NEXT''' DROP
'''NEXT''' SWAP DROP
'''IF''' DUP IM '''THEN''' s SWAP C→R SUB + '''ELSE''' DROP '''END'''
'''END'''
≫ ≫ '<span style="color:blue">BIGSUB</span>' STO
=={{header|Ruby}}==
===Brute Force:===
Answer is stored in "slice". It is very slow O(n**3)
<
max, slice = 0, []
arr.each_index do |i|
Line 2,946 ⟶ 3,525:
end
[max, slice]
end</
'''Test:'''
<
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],
[-1, -2, -3, -4, -5],
Line 2,955 ⟶ 3,534:
puts "\nInput seq: #{input}"
puts " Max sum: %d\n Subseq: %s" % subarray_sum(input)
end</
{{out}}
<pre>
Line 2,978 ⟶ 3,557:
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
Line 2,999 ⟶ 3,578:
end
return max, arr[first..last]
end</
The test result is the same above.
=={{header|Run BASIC}}==
<
max = -999
for i = 1 to 11
Line 3,020 ⟶ 3,599:
print word$(seq$,i,",");",";
next i
print " = ";max</
{{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];
Line 3,045 ⟶ 3,623:
println!("Max subsequence sum: {} for {:?}", max, &nums[boundaries]);;
}</
{{out}}
<pre>Max subsequence sum: 96 for [1, 2, 39, 34, 20]</pre>
Line 3,056 ⟶ 3,634:
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
Line 3,080 ⟶ 3,658:
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))
Line 3,093 ⟶ 3,671:
(loop sum seq sum seq (cdr l))
(loop sum seq maxsum maxseq (cdr l)))
(loop 0 (list) 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
Line 3,144 ⟶ 3,722:
end for;
writeln;
end func;</
{{out}}
<pre>
Line 3,152 ⟶ 3,730:
=={{header|Sidef}}==
{{trans|
<
var (start, end, sum, maxsum) = (-1, -1, 0, 0)
a.each_kv { |i, x|
sum += x
if (maxsum < sum) {
maxsum = sum
end = i
}
elsif (sum < 0) {
sum = 0
start = i
}
}
a.
}
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)
say maxsubseq(-2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1)
{{out}}
Line 3,178 ⟶ 3,756:
[3, 5, 6, -1, 4]
[]
</pre>
=={{header|SparForte}}==
As a structured script.
<syntaxhighlight lang="ada">#!/usr/local/bin/spar
pragma annotate( summary, "gss" )
@( description, "greatest sequential sum" )
@( description, "Given a sequence of integers, find a continuous subsequence which maximizes the" )
@( description, "sum of its elements, that is, the elements of no other single subsequence add" )
@( description, "up to a value larger than this one. An empty subsequence is considered to have" )
@( description, "the sum 0; thus if all elements are negative, the result must be the empty" )
@( description, "sequence." )
@( see_also, "http://rosettacode.org/wiki/Greatest_subsequential_sum" )
@( author, "Ken O. Burtch" );
pragma license( unrestricted );
pragma restriction( no_external_commands );
procedure gss is
type int_array is array( 1..11 ) of integer;
a : constant int_array := (-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1);
length : constant integer := arrays.length( a );
beginmax : integer := 0;
endmax : integer := -1;
maxsum : integer := 0;
running_sum : integer := 0;
begin
for start in arrays.first(a)..length-1 loop
running_sum := 0;
for finish in start..length-1 loop
running_sum := @ + a(finish);
if running_sum > maxsum then
maxsum := running_sum;
beginmax := start;
endmax := finish;
end if;
end loop;
end loop;
for i in beginmax..endmax loop
? a(i);
end loop;
end gss;</syntaxhighlight>
=={{header|SQL}}==
{{works with|ORACLE 19c}}
This is not a particularly efficient solution, but it gets the job done.
<syntaxhighlight lang="sql">
/*
This is a code implementation for finding one or more contiguous subsequences in a general sequence with the maximum sum of its elements.
p_list -- List of elements of the general sequence of integers separated by a delimiter.
p_delimiter -- proper delimiter
*/
with
function greatest_subsequential_sum(p_list in varchar2, p_delimiter in varchar2) return varchar2 is
-- Variablen
v_list varchar2(32767) := trim(both p_delimiter from p_list);
v_substr_i varchar2(32767);
v_substr_j varchar2(32767);
v_substr_out varchar2(32767);
v_res integer := 0;
v_res_out integer := 0;
--
begin
--
v_list := regexp_replace(v_list,''||chr(92)||p_delimiter||'{2,}',p_delimiter);
--
for i in 1..nvl(regexp_count(v_list,'[^'||p_delimiter||']+'),0)
loop
v_substr_i := substr(v_list,regexp_instr(v_list,'[^'||p_delimiter||']+',1,i));
--
for j in reverse 1..regexp_count(v_substr_i,'[^'||p_delimiter||']+')
loop
--
v_substr_j := trim(both p_delimiter from substr(v_substr_i,1,regexp_instr(v_substr_i,'[^'||p_delimiter||']+',1,j,1)));
execute immediate 'select sum('||replace(v_substr_j,p_delimiter,'+')||') from dual' into v_res;
--
if v_res > v_res_out then
v_res_out := v_res;
v_substr_out := '{'||v_substr_j||'}';
elsif v_res = v_res_out then
v_res_out := v_res;
v_substr_out := v_substr_out||',{'||v_substr_j||'}';
end if;
--
end loop;
--
end loop;
--
v_substr_out := trim(both ',' from nvl(v_substr_out,'{}'));
v_substr_out := case when regexp_count(v_substr_out,'},{')>0 then 'subsequences '||v_substr_out else 'a subsequence '||v_substr_out end;
return 'The maximum sum '||v_res_out||' belongs to '||v_substr_out||' of the main sequence {'||p_list||'}';
end;
--Test
select greatest_subsequential_sum('-1|-2|-3|-4|-5|', '|') as "greatest subsequential sum" from dual
union all
select greatest_subsequential_sum('', '') from dual
union all
select greatest_subsequential_sum(' ', ' ') from dual
union all
select greatest_subsequential_sum(';;;;;;+1;;;;;;;;;;;;;2;+3;4;;;;-5;;;;', ';') from dual
union all
select greatest_subsequential_sum('-1,-2,+3,,,,,,,,,,,,+5,+6,-2,-1,+4,-4,+2,-1', ',') from dual
union all
select greatest_subsequential_sum(',+7,-6,-8,+5,-2,-6,+7,+4,+8,-9,-3,+2,+6,-4,-6,,', ',') from dual
union all
select greatest_subsequential_sum('01 +2 3 +4 05 -8 -9 -20 40 25 -5', ' ') from dual
union all
select greatest_subsequential_sum('1 2 3 0 0 -99 02 03 00001 -99 3 2 1 -99 3 1 2 0', ' ') from dual
union all
select greatest_subsequential_sum('0,0,1,0', ',') from dual
union all
select greatest_subsequential_sum('0,0,0', ',') from dual
union all
select greatest_subsequential_sum('1,-1,+1', ',') from dual;
</syntaxhighlight>
{{out}}
<pre>
The maximum sum 0 belongs to a subsequence {} of the main sequence {-1|-2|-3|-4|-5|}
The maximum sum 0 belongs to a subsequence {} of the main sequence {}
The maximum sum 0 belongs to a subsequence {} of the main sequence { }
The maximum sum 10 belongs to a subsequence {+1;2;+3;4} of the main sequence {;;;;;;+1;;;;;;;;;;;;;2;+3;4;;;;-5;;;;}
The maximum sum 15 belongs to a subsequence {+3,+5,+6,-2,-1,+4} of the main sequence {-1,-2,+3,,,,,,,,,,,,+5,+6,-2,-1,+4,-4,+2,-1}
The maximum sum 19 belongs to a subsequence {+7,+4,+8} of the main sequence {,+7,-6,-8,+5,-2,-6,+7,+4,+8,-9,-3,+2,+6,-4,-6,,}
The maximum sum 65 belongs to a subsequence {40 25} of the main sequence {01 +2 3 +4 05 -8 -9 -20 40 25 -5}
The maximum sum 6 belongs to subsequences {1 2 3 0 0},{1 2 3 0},{1 2 3},{02 03 00001},{3 2 1},{3 1 2 0},{3 1 2} of the main sequence {1 2 3 0 0 -99 02 03 00001 -99 3 2 1 -99 3 1 2 0}
The maximum sum 1 belongs to subsequences {0,0,1,0},{0,0,1},{0,1,0},{0,1},{1,0},{1} of the main sequence {0,0,1,0}
The maximum sum 0 belongs to subsequences {0,0,0},{0,0},{0},{0,0},{0},{0} of the main sequence {0,0,0}
The maximum sum 1 belongs to subsequences {1,-1,+1},{1},{+1} of the main sequence {1,-1,+1}
</pre>
=={{header|Standard ML}}==
<
fun loop (_, _, maxsum, maxseq) [] = (maxsum, rev maxseq)
| loop (sum, seq, maxsum, maxseq) (x::xs) = let
Line 3,198 ⟶ 3,916:
end;
maxsubseq [~1, ~2, 3, 5, 6, ~2, ~1, 4, ~4, 2, ~1]</
This returns a pair of the maximum sum and (one of) the maximum subsequence(s).
=={{header|Swift}}==
{{trans|C}}
<syntaxhighlight lang="swift">func maxSubseq(sequence: [Int]) -> (Int, Int, Int) {
var maxSum = 0, thisSum = 0, i = 0
var start = 0, end = -1
for (j, seq) in sequence.enumerated() {
thisSum += seq
if thisSum < 0 {
i = j + 1
thisSum = 0
} else if (thisSum > maxSum) {
maxSum = thisSum
start = i
end = j
}
}
return start <= end && start >= 0 && end >= 0
? (start, end + 1, maxSum) : (0, 0, 0)
}
let a = [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
let (start, end, maxSum) = maxSubseq(sequence: a)
print("Max sum = \(maxSum)")
print(a[start..<end])</syntaxhighlight>
{{out}}
<pre>
Max sum = 15
[3, 5, 6, -2, -1, 4]
</pre>
=={{header|Tcl}}==
<
set a {-1 -2 3 5 6 -2 -1 4 -4 2 -1}
Line 3,270 ⟶ 4,019:
puts [time {maxsumseq1 $a} 1000]
puts "maxsumseq2: [maxsumseq2 $a]"
puts [time {maxsumseq2 $a} 1000]</
{{out}}
<pre>sequence: -1 -2 3 5 6 -2 -1 4 -4 2 -1
Line 3,280 ⟶ 4,029:
=={{header|Ursala}}==
This example solves the problem by the naive algorithm of testing all possible subsequences.
<
#import int
Line 3,287 ⟶ 4,036:
#cast %zL
example = max_subsequence <-1,-2,3,5,6,-2,-1,4,-4,2,-1></
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.
Line 3,302 ⟶ 4,051:
<pre>
<3,5,6,-2,-1,4></pre>
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="wren">var gss = Fn.new { |s|
var best = 0
var start = 0
var end = 0
var sum = 0
var sumStart = 0
var i = 0
for (x in s) {
sum = sum + x
if (sum > best) {
best = sum
start = sumStart
end = i + 1
} else if (sum < 0) {
sum = 0
sumStart = i + 1
}
i = i + 1
}
return [s[start...end], best]
}
var tests = [
[-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1],
[-1, 1, 2, -5, -6],
[],
[-1, -2, -1]
]
for (test in tests) {
System.print("Input: %(test)")
var res = gss.call(test)
var subSeq = res[0]
var sum = res[1]
System.print("Sub seq: %(subSeq)")
System.print("Sum: %(sum)\n")
}</syntaxhighlight>
{{out}}
<pre>
Input: [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]
Sub seq: [3, 5, 6, -2, -1, 4]
Sum: 15
Input: [-1, 1, 2, -5, -6]
Sub seq: [1, 2]
Sum: 3
Input: []
Sub seq: []
Sum: 0
Input: [-1, -2, -1]
Sub seq: []
Sum: 0
</pre>
=={{header|XPL0}}==
<
int Array, Size, Sum, Best, I, Lo, Hi, BLo, BHi;
Line 3,327 ⟶ 4,134:
CrLf(0);
Text(0, "Sum = "); IntOut(0, Best); CrLf(0);
]</
{{out}}
Line 3,338 ⟶ 4,145:
=={{header|zkl}}==
{{trans|F#}}
<
s.reduce(fcn([(sum, seq, maxsum, maxseq)], x){
sum=sum+x; seq=T(x).extend(seq);
Line 3,346 ⟶ 4,153:
},
T(0,T,0,T))[3].reverse(); // -->maxseq.reverse()
}</
<
println(s.sum()," : ",s);
s:=maxsubseq(T(-1,-2)); println(s.sum()," : ",s);
s:=maxsubseq(T); println(s.sum()," : ",s);</
{{out}}
<pre>
Line 3,362 ⟶ 4,169:
=={{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
Line 3,389 ⟶ 4,196:
260 NEXT i
270 PRINT "]"
280 NEXT n</
|