Anonymous user
Greatest subsequential sum: Difference between revisions
no edit summary
SqrtNegInf (talk | contribs) m (→{{header|Sidef}}: Fix link: Perl 6 --> Raku) |
No edit summary |
||
Line 861:
[ 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)
<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</lang>
===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.
<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</lang>
'''Test:'''
<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</lang>
{{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>
| |||