Difference between revisions of "TADM2E 8.21"
From Algorithm Wiki
(Removes an incorrect solution and presents what I believe is a correct O(n) solution to the max-range problem, with test cases.) |
m (Minor code formatting fixes. Still looks a little wiggy.) |
||
| Line 14: | Line 14: | ||
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]) == 15 |
| − | assert max_range([-1, -2, -3, -4, -5]) == 0 | + | 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]) == 187 |
| − | assert max_range([31, -41, 59, 26, -53, 58, 97, -93, -23, 84, -200, 3]) == 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([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 | + | assert max_range([-100, 40, 5, -100, 11, -1, 11, -1, 11, -1, 11, -1, 11, -1]) == 51 |
Revision as of 18:32, 20 October 2017
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
