Anonymous user
Greatest subsequential sum: Difference between revisions
m
{{out}}
No edit summary |
m ({{out}}) |
||
Line 1:
{{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.
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}}==
Line 76 ⟶ 77:
)</lang>
{{out}}
<pre>
+3 +5 +6 -2 -1 +4
Line 135 ⟶ 136:
</lang>
{{out}}
+>Maximal subsequence: [+3,+5,+6,-2,-1,+4]
!>SUM of subsequence: 15
Line 203 ⟶ 205:
}</lang>
{{out}}
Maximal subsequence: [], sum 0
Array: [0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2]
Line 247 ⟶ 250:
NEXT
= LEFT$(LEFT$(a$)) + "]"</lang>
{{out}}
<pre>
[0, 1, 2, -3, 3, -1, 0, -4, 0, -1, -4, 2] -> [0, 1, 2]
Line 308 ⟶ 311:
[Ctrl-Q]OvctGreatestSubsequentialSum.Do -1 -5 -3 ~
</pre>
{{out}}
<pre>
[ 3, 5, 6, -2, -1, 4]= 15
Line 393 ⟶ 396:
return 0;
}</lang>
{{out}}
<pre>Max sum = 15
3 5 6 -2 -1 4 </pre>
Line 532 ⟶ 535:
(apply max-key #(reduce + %)))) ; max sum</lang>
{{out}}
<lang clojure>user> (max-subseq-sum [-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1])
[3 5 6 -2 -1 4]</lang>
Line 648 ⟶ 651:
===Alternative Version===
{{trans|Haskell}}
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;
Line 836 ⟶ 842:
? maxSubseq({-1, -5, -3})</lang>
{{out}}
<pre>{3,5,6,-2,-1,4}
{}
Line 854 ⟶ 860:
printfn "%A" (maxsubseq [-1 ; -2 ; 3 ; 5 ; 6 ; -2 ; -1 ; 4; -4 ; 2 ; -1])</lang>
{{out}}
<pre>[3; 5; 6; -2; -1; 4]</pre>
Line 953 ⟶ 959:
}
}</lang>
{{out}}
<pre>
Input: [-1 -2 3 5 6 -2 -1 4 -4 2 -1]
Line 1,023 ⟶ 1,029:
)</lang>
<tt>y</tt> is the input vector, an integer list.<br>
Each row indicates one sub-sequence; the count of columns equals the length of the input.
<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>
<br>All solutions are found but only one is returned, to fit the output requirement. 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.▼
All solutions are found but only one is returned, to fit the output requirement.
<br>Example use:▼
▲
<lang j> maxss _1 _2 3 5 6 _2 _1 4 _4 2 _1
3 5 6 _2 _1 4</lang>
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>
Line 1,523 ⟶ 1,532:
GreatestSubsequentialSum -1 -5 -3
</pre>
{{out}}
<pre>
[3,5,6,-2,-1,4]: 15
Line 1,634 ⟶ 1,643:
writeln (maxSum);
end.</lang>
{{out}}
<pre>:> ./GreatestSubsequentialSum
Sequence:
Line 1,666 ⟶ 1,675:
print "seq: @a\nmax: [ @{[max_sub @a]} ]\n";
print "seq: @b\nmax: [ @{[max_sub @b]} ]\n";</lang>
{{out}}
<pre>
seq: -7 5 -3 0 5 -5 -1 -1 -5 1
Line 1,742 ⟶ 1,752:
max_sub-seq( -2, -2, -1, -3, -5, -6, -1, -4, -4, -2, -1 ).perl.say;</lang>
{{out}}
[3, 5, 6, -2, -1, 4]
[3, 5, 6, -1, 4]
Line 1,789 ⟶ 1,800:
?>
</lang>
<lang>
0 15 3 -9 12
Line 1,800 ⟶ 1,811:
(mapcon '((L) (maplist reverse (reverse L)))
(-1 -2 3 5 6 -2 -1 4 -4 2 -1) ) )</lang>
{{out}}
<pre>-> (3 5 6 -2 -1 4)</pre>
Line 1,845 ⟶ 1,856:
End;
End;</lang>
{{out}}
<pre>
Sequence:
Line 1,913 ⟶ 1,924:
memoseq(DC, LC, TTC), gss(_D, _L, TT) <=> TTC > TT |
gss(DC, LC, TTC).</lang>
{{out}}
<pre> ?- greatest_subsequence.
[-1,-2,3,5,6,-2,-1,4,-4,2,-1]
Line 2,031 ⟶ 2,042:
if (end >= begin) x[begin:end] else x[c()]
}</lang>
{{out}}
<lang r>> max.subseq(c(-1, -2, 3, 5, 6, -2, -1, 4, -4, 2, -1))
[1] 3 5 6 -2 -1 4</lang>
Line 2,098 ⟶ 2,109:
say; say 'sum='word(sum 0,1)/1 " sequence="seq
/*stick a fork in it, we're done.*/</lang>
<pre>
words=11 list=-1 -2 3 5 6 -2 -1 4 -4 2 -1
Line 2,104 ⟶ 2,115:
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,130 ⟶ 2,141:
say; say 'sum='word(sum 0,1)/1 " sequence="seq
/*stick a fork in it, we're done.*/</lang>
<pre>
words=12 list=1 2 3 4 0 -777 1 2 3 4 0 0
Line 2,169 ⟶ 2,180:
Say 'Sum:' maxSum
End</lang>
{{out}}
<pre>
Sequence:
Line 2,248 ⟶ 2,259:
next i
print " = ";max</lang>
{{out}}
<pre>Sum: 3, 5, 6, -2, -1, 4, = 15</pre>
Line 2,347 ⟶ 2,358:
writeln;
end func;</lang>
{{out}}
<pre>
Maximal subsequence: 3 5 6 -2 -1 4
Line 2,444 ⟶ 2,455:
puts "maxsumseq2: [maxsumseq2 $a]"
puts [time {maxsumseq2 $a} 1000]</lang>
{{out}}
<pre>sequence: -1 -2 3 5 6 -2 -1 4 -4 2 -1
maxsumseq1: 3 5 6 -2 -1 4
Line 2,472 ⟶ 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 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}}
<pre>
<3,5,6,-2,-1,4></pre>
Line 2,502 ⟶ 2,513:
]</lang>
{{out}}
<pre>
Sequence = -1 -2 3 5 6 -2 -1 4 -4 2 -1
| |||