Greatest subsequential sum: Difference between revisions
Content added Content deleted
No edit summary |
m ({{out}}) |
||
Line 1: | Line 1: | ||
{{task}}[[Category:Arithmetic operations]] |
{{task}}[[Category:Arithmetic operations]] |
||
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. |
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. <br> |
||
An empty subsequence is considered to have the sum 0; thus if all elements are negative, the result must be the empty sequence. |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
Line 76: | Line 77: | ||
)</lang> |
)</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
+3 +5 +6 -2 -1 +4 |
+3 +5 +6 -2 -1 +4 |
||
Line 135: | Line 136: | ||
</lang> |
</lang> |
||
{{out}} |
|||
<pre>> Array: [-1,-2,+3,+5,+6,-2,-1,+4,-4,+2,-1] |
|||
+>Maximal subsequence: [+3,+5,+6,-2,-1,+4] |
+>Maximal subsequence: [+3,+5,+6,-2,-1,+4] |
||
!>SUM of subsequence: 15 |
!>SUM of subsequence: 15 |
||
Line 203: | Line 205: | ||
}</lang> |
}</lang> |
||
{{out}} |
|||
<pre>Array: [-1, -2, -3, -4, -5] |
|||
Maximal subsequence: [], sum 0 |
Maximal subsequence: [], sum 0 |
||
Array: [0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] |
Array: [0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] |
||
Line 247: | Line 250: | ||
NEXT |
NEXT |
||
= LEFT$(LEFT$(a$)) + "]"</lang> |
= LEFT$(LEFT$(a$)) + "]"</lang> |
||
{{out}} |
|||
'''Output:''' |
|||
<pre> |
<pre> |
||
[0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] -> [0, 1, 2] |
[0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] -> [0, 1, 2] |
||
Line 308: | Line 311: | ||
[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -5 -3 ~ |
[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -5 -3 ~ |
||
</pre> |
</pre> |
||
{{out}} |
|||
Output: <br/> |
|||
<pre> |
<pre> |
||
[ 3, 5, 6, -2, -1, 4]= 15 |
[ 3, 5, 6, -2, -1, 4]= 15 |
||
Line 393: | Line 396: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>Max sum = 15 |
<pre>Max sum = 15 |
||
3 5 6 -2 -1 4 </pre> |
3 5 6 -2 -1 4 </pre> |
||
Line 532: | Line 535: | ||
(apply max-key #(reduce + %)))) ; max sum</lang> |
(apply max-key #(reduce + %)))) ; max sum</lang> |
||
{{out}} |
|||
Sample output: |
|||
<lang clojure>user> (max-subseq-sum [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]) |
<lang clojure>user> (max-subseq-sum [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1]) |
||
[3 5 6 -2 -1 4]</lang> |
[3 5 6 -2 -1 4]</lang> |
||
Line 648: | Line 651: | ||
===Alternative Version=== |
===Alternative Version=== |
||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
This version is much less efficient. The output is similar. |
This version is much less efficient. The output is similar. |
||
Currently the D standard library lacks the sum, inits, tails functions, |
|||
and max can't be used as the maximumBy functions |
|||
(for the concatMap a map.join is enough). |
|||
<lang d>import std.stdio, std.algorithm, std.range, std.typecons; |
<lang d>import std.stdio, std.algorithm, std.range, std.typecons; |
||
Line 836: | Line 842: | ||
? maxSubseq({-1, -5, -3})</lang> |
? maxSubseq({-1, -5, -3})</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>{3,5,6,-2,-1,4} |
<pre>{3,5,6,-2,-1,4} |
||
{} |
{} |
||
Line 854: | Line 860: | ||
printfn "%A" (maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1])</lang> |
printfn "%A" (maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1])</lang> |
||
{{out}} |
|||
Output |
|||
<pre>[3; 5; 6; -2; -1; 4]</pre> |
<pre>[3; 5; 6; -2; -1; 4]</pre> |
||
Line 953: | Line 959: | ||
} |
} |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Input: [-1 -2 3 5 6 -2 -1 4 -4 2 -1] |
Input: [-1 -2 3 5 6 -2 -1 4 -4 2 -1] |
||
Line 1,023: | Line 1,029: | ||
)</lang> |
)</lang> |
||
<tt>y</tt> is the input vector, an integer list. |
<tt>y</tt> is the input vector, an integer list.<br> |
||
<tt>AS</tt> means "all sub-sequences." It is a binary table. |
|||
Each row indicates one sub-sequence; the count of columns equals the length of the input. |
|||
<br><tt>MX</tt> means "maxima." It is the first location in <tt>AS</tt> where the corresponding sum is largest. |
|||
<br> |
<br><tt>MX</tt> means "maxima." It is the first location in <tt>AS</tt> where the corresponding sum is largest. <br> |
||
Totals for the subsequences are calculated by the phrase '<tt>AS +/ . * y</tt>' which is the inner product of the binary table with the input vector. <br> |
|||
⚫ | |||
All solutions are found but only one is returned, to fit the output requirement. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
<lang j> maxss _1 _2 3 5 6 _2 _1 4 _4 2 _1 |
<lang j> maxss _1 _2 3 5 6 _2 _1 4 _4 2 _1 |
||
3 5 6 _2 _1 4</lang> |
3 5 6 _2 _1 4</lang> |
||
Note: if we just want the sum of the maximum subsequence, |
Note: if we just want the sum of the maximum subsequence, |
||
and are not concerned with the subsequence itself, we can use: |
|||
<lang j>maxs=: [:>./(0>.+)/\.</lang> |
<lang j>maxs=: [:>./(0>.+)/\.</lang> |
||
Line 1,523: | Line 1,532: | ||
GreatestSubsequentialSum -1 -5 -3 |
GreatestSubsequentialSum -1 -5 -3 |
||
</pre> |
</pre> |
||
{{out}} |
|||
Output:<br/> |
|||
<pre> |
<pre> |
||
[3,5,6,-2,-1,4]: 15 |
[3,5,6,-2,-1,4]: 15 |
||
Line 1,634: | Line 1,643: | ||
writeln (maxSum); |
writeln (maxSum); |
||
end.</lang> |
end.</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>:> ./GreatestSubsequentialSum |
<pre>:> ./GreatestSubsequentialSum |
||
Sequence: |
Sequence: |
||
Line 1,666: | Line 1,675: | ||
print "seq: @a\nmax: [ @{[max_sub @a]} ]\n"; |
print "seq: @a\nmax: [ @{[max_sub @a]} ]\n"; |
||
print "seq: @b\nmax: [ @{[max_sub @b]} ]\n";</lang> |
print "seq: @b\nmax: [ @{[max_sub @b]} ]\n";</lang> |
||
{{out}} |
|||
<pre> |
<pre> |
||
seq: -7 5 -3 0 5 -5 -1 -1 -5 1 |
seq: -7 5 -3 0 5 -5 -1 -1 -5 1 |
||
Line 1,742: | Line 1,752: | ||
max_sub-seq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).perl.say;</lang> |
max_sub-seq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).perl.say;</lang> |
||
{{out}} |
|||
<pre> |
|||
[3, 5, 6, -2, -1, 4] |
[3, 5, 6, -2, -1, 4] |
||
[3, 5, 6, -1, 4] |
[3, 5, 6, -1, 4] |
||
Line 1,789: | Line 1,800: | ||
?> |
?> |
||
</lang> |
</lang> |
||
{{out}} in browser: |
|||
<lang> |
<lang> |
||
0 15 3 -9 12 |
0 15 3 -9 12 |
||
Line 1,800: | Line 1,811: | ||
(mapcon '((L) (maplist reverse (reverse L))) |
(mapcon '((L) (maplist reverse (reverse L))) |
||
(-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )</lang> |
(-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>-> (3 5 6 -2 -1 4)</pre> |
<pre>-> (3 5 6 -2 -1 4)</pre> |
||
Line 1,845: | Line 1,856: | ||
End; |
End; |
||
End;</lang> |
End;</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Sequence: |
Sequence: |
||
Line 1,913: | Line 1,924: | ||
memoseq(DC, LC, TTC), gss(_D, _L, TT) <=> TTC > TT | |
memoseq(DC, LC, TTC), gss(_D, _L, TT) <=> TTC > TT | |
||
gss(DC, LC, TTC).</lang> |
gss(DC, LC, TTC).</lang> |
||
{{out}} |
|||
OutPut: |
|||
<pre> ?- greatest_subsequence. |
<pre> ?- greatest_subsequence. |
||
[-1,-2,3,5,6,-2,-1,4,-4,2,-1] |
[-1,-2,3,5,6,-2,-1,4,-4,2,-1] |
||
Line 2,031: | Line 2,042: | ||
if (end >= begin) x[begin:end] else x[c()] |
if (end >= begin) x[begin:end] else x[c()] |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
Sample output: |
|||
<lang r>> max.subseq(c(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1)) |
<lang r>> max.subseq(c(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1)) |
||
[1] 3 5 6 -2 -1 4</lang> |
[1] 3 5 6 -2 -1 4</lang> |
||
Line 2,098: | Line 2,109: | ||
say; say 'sum='word(sum 0,1)/1 " sequence="seq |
say; say 'sum='word(sum 0,1)/1 " sequence="seq |
||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
{{out}} when the following was used for the list: <tt>-1 -2 3 5 6 -2 -1 4 -4 2 -1</tt> |
|||
<pre> |
<pre> |
||
words=11 list=-1 -2 3 5 6 -2 -1 4 -4 2 -1 |
words=11 list=-1 -2 3 5 6 -2 -1 4 -4 2 -1 |
||
Line 2,104: | Line 2,115: | ||
sum=15 sequence=3 5 6 -2 -1 4 |
sum=15 sequence=3 5 6 -2 -1 4 |
||
</pre> |
</pre> |
||
{{out}} when the following was used for the list: <tt>1 2 3 4 -777 1 2 3 4 0 0</tt> |
|||
<pre> |
<pre> |
||
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0 |
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0 |
||
Line 2,130: | Line 2,141: | ||
say; say 'sum='word(sum 0,1)/1 " sequence="seq |
say; say 'sum='word(sum 0,1)/1 " sequence="seq |
||
/*stick a fork in it, we're done.*/</lang> |
/*stick a fork in it, we're done.*/</lang> |
||
{{out}} when the following was used for the list: <tt>1 2 3 4 -777 1 2 3 4 0 0</tt> |
|||
<pre> |
<pre> |
||
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0 |
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0 |
||
Line 2,169: | Line 2,180: | ||
Say 'Sum:' maxSum |
Say 'Sum:' maxSum |
||
End</lang> |
End</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Sequence: |
Sequence: |
||
Line 2,248: | Line 2,259: | ||
next i |
next i |
||
print " = ";max</lang> |
print " = ";max</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>Sum: 3, 5, 6, -2, -1, 4, = 15</pre> |
<pre>Sum: 3, 5, 6, -2, -1, 4, = 15</pre> |
||
Line 2,347: | Line 2,358: | ||
writeln; |
writeln; |
||
end func;</lang> |
end func;</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Maximal subsequence: 3 5 6 -2 -1 4 |
Maximal subsequence: 3 5 6 -2 -1 4 |
||
Line 2,444: | Line 2,455: | ||
puts "maxsumseq2: [maxsumseq2 $a]" |
puts "maxsumseq2: [maxsumseq2 $a]" |
||
puts [time {maxsumseq2 $a} 1000]</lang> |
puts [time {maxsumseq2 $a} 1000]</lang> |
||
{{out}} |
|||
outputs |
|||
<pre>sequence: -1 -2 3 5 6 -2 -1 4 -4 2 -1 |
<pre>sequence: -1 -2 3 5 6 -2 -1 4 -4 2 -1 |
||
maxsumseq1: 3 5 6 -2 -1 4 |
maxsumseq1: 3 5 6 -2 -1 4 |
||
Line 2,472: | Line 2,483: | ||
* The list lead operator <code>y</code> by itself takes a non-empty list as an argument and returns a copy with the last item deleted. |
* The list lead operator <code>y</code> by itself takes a non-empty list as an argument and returns a copy with the last item deleted. |
||
* The triangle-squared combinator <code>K33</code> constructs a function that takes an input list of a length <math>n</math>, constructs a list of <math>n</math> copies of it, and applies its operand 0 times to the head, once to the head of tail, twice to the head of the tail of the tail, and so on. Hence, an operand of <code>y</code> will generate the list of all prefixes of a list. |
* The triangle-squared combinator <code>K33</code> constructs a function that takes an input list of a length <math>n</math>, constructs a list of <math>n</math> copies of it, and applies its operand 0 times to the head, once to the head of tail, twice to the head of the tail of the tail, and so on. Hence, an operand of <code>y</code> will generate the list of all prefixes of a list. |
||
{{out}} |
|||
output: |
|||
<pre> |
<pre> |
||
<3,5,6,-2,-1,4></pre> |
<3,5,6,-2,-1,4></pre> |
||
Line 2,502: | Line 2,513: | ||
]</lang> |
]</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
Sequence = -1 -2 3 5 6 -2 -1 4 -4 2 -1 |
Sequence = -1 -2 3 5 6 -2 -1 4 -4 2 -1 |