4.1 The maximum-subarray problem
4.1-1
It returns the index and value of the biggest negative number in A.
4.1-2
FIND-MAXIMUM-SUBARRAY-BRUTE-FORCE(A, low, high)
max = -∞
start = -1, end = -1
for i = low to high
sum = 0
for j = i to high
sum += A[j]
if sum > max
max = sum
start = i
end = j
return (start, end, max)
4.1-3
Brute force:
def find_maximum_subarray_brute_force(numbers, low, high):
start = -1
end = -1
max_sum = -float('inf')
for i in range(low, high + 1):
current_sum = 0
for j in range(i, high + 1):
current_sum += numbers[j]
if current_sum > max_sum:
max_sum = current_sum
start, end = i, j
return (start, end, max_sum)
Divide and conquer:
def find_maximum_subarray_divide_and_conquer(numbers, low, high):
if len(numbers) == 0:
return (-1, -1, -float('inf'))
elif low == high:
return (low, high, numbers[low])
else:
middle = (low + high) // 2
left_maximum_subarray = find_maximum_subarray_divide_and_conquer(
numbers, low, middle)
right_maximum_subarray = find_maximum_subarray_divide_and_conquer(
numbers, middle + 1, high)
cross_maximum_subarray = find_max_crossing_subarray(
numbers, low, middle, high)
if (left_maximum_subarray[2] >= right_maximum_subarray[2] and
left_maximum_subarray[2] >= cross_maximum_subarray[2]):
return left_maximum_subarray
elif (right_maximum_subarray[2] >= left_maximum_subarray[2] and
right_maximum_subarray[2] >= cross_maximum_subarray[2]):
return right_maximum_subarray
else:
return cross_maximum_subarray
def find_max_crossing_subarray(numbers, low, middle, high):
start = middle
end = middle
current_sum = 0
left_sum = -float('inf')
right_sum = -float('inf')
for i in range(middle, low - 1, -1):
current_sum += numbers[i]
if current_sum > left_sum:
left_sum = current_sum
start = i
current_sum = 0
for i in range(middle + 1, high + 1):
current_sum += numbers[i]
if current_sum > right_sum:
right_sum = current_sum
end = i
return (start, end, left_sum + right_sum)
In my env, when $n_0 = 64$ gives the crossover point. I changed the base of the recursive algorithm, but that doesn't change the crossover point.
4.1-4
Currently the implementation already supports empty array, but it returns (-1, -1, -float('inf'))
, we can change it to an empty array.
4.1-5
def find_maximum_subarray_linear_time(numbers, low, high):
if len(numbers) == 0:
return (-1, -1, -float('inf'))
start = -1
max_sum_start = -1
max_sum_end = -1
max_sum_so_far = -float('inf')
max_sum_ending_here = -float('inf')
for i in range(low, high + 1):
if numbers[i] > max_sum_ending_here + numbers[i]:
max_sum_ending_here = numbers[i]
start = i
else:
max_sum_ending_here += numbers[i]
if max_sum_ending_here > max_sum_so_far:
max_sum_so_far = max_sum_ending_here
max_sum_start = start
max_sum_end = i
return (max_sum_start, max_sum_end, max_sum_so_far)