|
|
| Line 1: |
Line 1: |
| − | ==== 1 ====
| |
| | | | |
| − | Sum every range and keep track of the maximum.
| |
| − |
| |
| − | Given a set of numbers N = { x0, x1 ... xn }
| |
| − |
| |
| − | M = 0
| |
| − |
| |
| − | for i in (0 .. n)
| |
| − | S[i, i] = xi
| |
| − | for j in (i + 1 .. n)
| |
| − | S[i, j] = S[i, j - 1] + xj
| |
| − | if M < S[i, j]
| |
| − | M = S[i, j]
| |
| − |
| |
| − | ==== 2 ====
| |
| − |
| |
| − | def max_range(items):
| |
| − | max_diff = max(items[0], 0)
| |
| − | temp_diff = 0
| |
| − | for number in items:
| |
| − | temp_diff = max(0, temp_diff + number)
| |
| − | max_diff = max(max_diff, temp_diff)
| |
| − | return max_diff
| |
| − |
| |
| − | assert max_range([1, 2, 3, 4, 5]) == 15
| |
| − | assert max_range([-1, -2, -3, -4, -5]) == 0
| |
| − | assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84]) == 187
| |
| − | assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 187
| |
| − | assert max_range([11, -1, 11, -1, 11, -1, 11, -1, 11, -1, -100, 40, 5]) == 51
| |
| − | assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51
| |
