Greatest subsequential sum: Difference between revisions
m
→{{header|EasyLang}}
(→{{header|RPL}}: HP-49 version) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 1,191:
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}}==
Line 3,095 ⟶ 3,128:
{{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}}==
Line 3,388 ⟶ 3,474:
1: { { } { 2 } { 2 -1 3 } { 1 2 } { 3 5 6 -2 -1 4 } }
</pre>
{{trans|Fortran}}
{{works with|HP|49}}
Line 3,405 ⟶ 3,491:
'''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
Line 3,945 ⟶ 4,051:
<pre>
<3,5,6,-2,-1,4></pre>
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var best = 0
var start = 0
Line 4,035 ⟶ 4,108:
Sub seq: []
Sum: 0
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang="xpl0">include c:\cxpl\codes;
int Array, Size, Sum, Best, I, Lo, Hi, BLo, BHi;
[Array:= [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1];
Size:= 11;
Best:= -100000;
for Lo:= 0 to Size-1 do
for Hi:= Lo to Size-1 do
[Sum:= 0;
for I:= Lo to Hi do
Sum:= Sum + Array(I);
if Sum > Best then
[Best:= Sum; BLo:= Lo; BHi:= Hi];
];
Text(0, "Sequence = ");
for I:= 0 to Size-1 do
[IntOut(0, Array(I)); Text(0, " ")];
CrLf(0);
Text(0, "Greatest = ");
for I:= BLo to BHi do
[IntOut(0, Array(I)); Text(0, " ")];
CrLf(0);
Text(0, "Sum = "); IntOut(0, Best); CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
Sequence = -1 -2 3 5 6 -2 -1 4 -4 2 -1
Greatest = 3 5 6 -2 -1 4
Sum = 15
</pre>
| |||