Algorithm 1 – O(n^2): enumerate all possible subarray
This is pretty straightforward, but second program improves the performance by not repeating calculating sum.
def max_subarray_enum(l):
"""
>>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_enum(l))
95
>>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_enum(l))
32
"""
length = len(l)
def sum(i, len):
# assertion
val = 0
for n in range(0, len):
val += l[i + n]
return val
# loop invariant:
# l[i:i+len] is subarray which we need to calculate the sum
# termination: enumerated all possible i j combinations
max_val = l[0]
for i in range(0, length):
for subarray_len in range(1, length - i + 1):
val = sum(i, subarray_len)
if val > max_val: max_val = val
return max_val
def max_subarray_enum2(l):
"""
>>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_enum2(l))
95
>>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_enum2(l))
32
"""
length = len(l)
# loop invariant:
# l[i:i+len] is subarray which we need to calculate the sum
# termination: enumerated all possible i j combinations
max_val = l[0]
for i in range(0, length):
val = 0
for subarray_len in range(1, length - i + 1):
val += l[i + subarray_len - 1]
if val > max_val: max_val = val
return max_val
Algorithm 2 – O(nlogn): divide and conquer
def max_subarray_divide(l, left, right):
"""
>>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_divide(l, 0, len(l) - 1))
95
>>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_divide(l, 0, len(l) - 1))
32
"""
# divide and conquer:
# max = max_val(
# recur(firsthalf),
# recur(secondhalf),
# max_sum_left + max_sum_right
# )
def max_val(vals):
# TODO: assert
max = vals[0]
for val in vals:
if max < val: max = val
return max
def max_sum(start, end, step):
if step > 0 and start > end:
return 0
elif step < 0 and end > start:
return 0
index_range = range(start, end + step, step)
max = l[index_range[0]]
sum = max
for i in index_range[1:]:
sum += l[i]
if max < sum: max = sum
return max
if left > right:
return 0 # actually, this one should be minus infinity
if left == right:
return l[left]
mid = left + ((right - left) >> 1)
# NOTE for the following statement, if we put max_sum(mid, right, 1)
# then there will be dead recursive loop
max_sum_right = max_sum(mid + 1, right, 1)
max_sum_left = max_sum(mid, left, -1)
max_sum_first = max_subarray_divide(l, left, mid)
max_sum_right = max_subarray_divide(l, mid + 1, right)
return max_val([max_sum_first, max_sum_right, max_sum_left + max_sum_right])
Algorithm 3 – O(n) with O(n) space: dynamic programming
def max_subarray(l):
"""
>>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray(l))
95
>>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray(l))
32
"""
# following are the dynamic programming vars:
# - tail_max[n] means max subarray that ends at position n
# - max[n] means max subarray in array l[0:n+1]
#
# following are the dynamic programming equations:
# - tail_max[n] = max(tail_max[n-1]+l[n], l[n])
# - max[n] = max(max[n-1], tail_max[n])
#
def max_val(a, b):
return a if a > b else b
# init data structures
length = len(l)
max = [None] * length
tail_max = [None] * length
# initial values
if len(l) == 0:
return 0
max[0] = l[0]
tail_max[0] = l[0]
# dynamic programming: loop
for n in range(1, length):
tail_max[n] = max_val(tail_max[n-1]+l[n], l[n])
max[n] = max_val(max[n-1], tail_max[n])
return max[n]
Algorithm 4 – O(n) with O(1) space: dynamic programming with improvement
def max_subarray_o1space(l):
"""
>>> l = [43, 23, -3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_o1space(l))
95
>>> l = [-3, 32, -43, -22, 12, 3, -4, 5]
>>> print(max_subarray_o1space(l))
32
"""
def max_val(a, b):
return a if a > b else b
# initial values
if len(l) == 0:
return 0
max_prev = l[0]
tail_max_prev = l[0]
# init data structures
max = max_prev
tail_max = tail_max_prev
# dynamic programming: loop
for n in range(1, len(l)):
tail_max = max_val(tail_max_prev+l[n], l[n])
max = max_val(max_prev, tail_max)
tail_max_prev = tail_max
max_prev = max
return max
2D array?…
OK, I’ll ignore the code here….but it can be converted to 1D array like:
for upper_bound in range(0, first_dim_length(matrix)):
for lower_bound in range(upper_bound, first_dim_length(matrix):
merge the 2D array in within upper and lower bound to 1D array
use dynamic programming approach to solve it