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)