max subarray

max_subarray.py

#!/bin/python3

from math import floor, ceil

def max_subarray_brute_force(A):
    '''
    Given a list, return a tuple (low_index, high_index, max_sum), where
    low_index and high_index give the starting and ending indices (both
    inclusive) of the maximum subarray, and max_sum gives the sum of
    that subarray.
    '''
    max_sum = A[0]
    low_index = 0
    high_index = 0
    for i in range(len(A)):
        loc_high_index = i
        loc_max = A[i]
        loc_sum = A[i]
        for j in range(i + 1, len(A)):
            loc_sum += A[j]
            if loc_sum > loc_max:
                loc_max = loc_sum
                loc_high_index = j
        if loc_max > max_sum:
            max_sum = loc_max
            low_index = i
            high_index = loc_high_index
    return (low_index, high_index, max_sum)

def find_max_crossing_subarray(A, low, mid, high):
    '''
    Implementation of Find-Max-Crossing-Subarray from CLRS pg 71.
    low and high are both inclusive
    '''
    left_sum = A[mid]
    sum = A[mid]
    max_left = mid
    for i in range(mid - 1, low - 1, -1):
        sum = sum + A[i]
        if sum > left_sum:
            left_sum = sum
            max_left = i
    right_sum = A[mid + 1]
    sum = A[mid + 1]
    max_right = mid + 1
    for j in range(mid + 2, high + 1):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
    return (max_left, max_right, left_sum + right_sum)

def find_maximum_subarray(A, low, high):
    '''
    Implementation of Find-Maximum-Subarray from CLRS pg 72.
    low and high inclusive
    '''
    if high == low:
        return (low, high, A[low])
    else:
        mid = floor((low + high) / 2)
        left_low, left_high, left_sum = find_maximum_subarray(A, low, mid)
        right_low, right_high, right_sum = find_maximum_subarray(A, mid + 1, high)
        cross_low, cross_high, cross_sum = find_max_crossing_subarray(A, low, mid, high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return (left_low, left_high, left_sum)
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return (right_low, right_high, right_sum)
        else:
            return (cross_low, cross_high, cross_sum)

def max_subarray_divide_and_conquer(A):
    return find_maximum_subarray(A, 1, len(A) - 1)

def max_subarray_linear(A):
    max = A[0]
    low_index = 0
    high_index = 0
    back_track_index = 0
    back_track_max = A[0]
    for j in range(len(A) - 1):
        if back_track_max > 0:
            back_track_max  += A[j + 1]
            if back_track_max > max:
                max = back_track_max
                low_index = back_track_index
                high_index = j + 1
        elif A[j + 1] > max:
            # So automatically A[j + 1] > back_track_max
            max = A[j + 1]
            low_index = j + 1
            high_index = j + 1
            back_track_max = A[j + 1]
            back_track_index = j + 1
        else:
            back_track_max = A[j + 1]
            back_track_index = j + 1
    return (low_index, high_index, max)

if __name__ == "__main__":
    A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
    lst = [max_subarray_brute_force(A), max_subarray_divide_and_conquer(A), max_subarray_linear(A)]
    for i in lst:
        print(i)
        print(A[i[0]:i[1] + 1])