max_sequence_sum
is a library extension to Array that finds the sequence with the largest sum inside an array (subarray).
It has methods to return the sum, the subarray and its initial and final positions.
Run bundle install
first.
require_relative "lib/max_sequence_sum"
- Array#max_slice_sum
# returns sum of subarray with largest sum
[2, -4, 6, 8, -10, 100, -6, 5].max_slice_sum
=> 104
- Array#max_sum_slice
# returns subarray with largest sum
[2, -4, 6, 8, -10, 100, -6, 5].max_sum_slice
=> [6, 8, -10, 100]
- Array#max_sum_slice_positions
# returns positions of subarray with largest sum
[2, -4, 6, 8, -10, 100, -6, 5].max_sum_slice_positions
=> [2,5]
- A different approach for each method: 9f173e2…
- A common approach for the methods: HEAD
- Optimized version: optimizations branch
It's an exhaustive solution. It runs on O(n^2), it's really not efficient for large arrays.
Take [ 10, -99, 5, 8 ]
as an example array.
- All subarrays are generated
[ [10], [-99], [5], [8], [10, -99], [-99, 5], [5, 8], [10, -99, 5], [-99, 5, 8], [10, -99, 5, 8] ]
- Then we compute the sum for the subarrays
[ [10], [-99], [5], [8], [10, -99], [-99, 5], [5, 8], [10, -99, 5], [-99, 5, 8], [10, -99, 5, 8] ]
| | | | | | | | | |
10 -99 5 8 -89 -94 13 -84 -86 -76
- Next we select the one with the largest sum
[ … [5, 8] … ]
|
13
- Finally we return it, along with its positions and sum
subarray = [5, 8]
positions = [2,4]
sum = 13