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
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent