Greatest subsequential sum: Difference between revisions
m
→{{header|EasyLang}}
No edit summary |
|||
| (9 intermediate revisions by 5 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,357 ⟶ 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}}==
Line 3,577 ⟶ 3,732:
{{trans|Raku}}
<syntaxhighlight lang="ruby">func maxsubseq(*a) {
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,896 ⟶ 4,051:
<pre>
<3,5,6,-2,-1,4></pre>
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var best = 0
var start = 0
Line 3,986 ⟶ 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>
| |||