The Maximum Subarray Sum problem is the task of finding the contiguous subarray with largest sum in a given array of integers. Each number in the array could be positive, negative, or zero.

For example: Given the array [−2, 1, −3, 4, −1, 2, 1, −5, 4] the solution would be [4, −1, 2, 1] with a sum of 6.

A Brute Force solution for this problem with complexity of O(n^2):

def maximum_subarray_sum_brute_force(arr):
    n = len(arr)
    if n == 0:
        return None
    
    temp_sum = max_sum = 0
    (start_index, end_index) = (0,0)

    for i in range(n):
        for j in range(i, n):
            temp_sum += arr[j]
            if(temp_sum > max_sum):
                max_sum = temp_sum
                (start_index , end_index) = (i,j)
        temp_sum = 0
    return (arr[start_index:(end_index+1)], max_sum)

Description:

This algorithm does comparisons for all subarrays in an array such as sum of 0, 0 ∼ 1, 0 ∼ 2, … 0 ∼ (n-1) for first loop, and then sum of 1, 1 ∼ 2, 1 ∼ 3, … 1 ∼ (n-1) for second loop, totally n such loops. So, its complexity is 

A Divide and Conquer solution for this problem with complexity O(n log n):

def maximum_subarray_sum_divide_conquer(arr, l, r):
      
    # If only 1 element
    if (l == r) : 
        return (arr[l:(r+1)], l, r, arr[l])
  
    # Find middle point 
    m = (l + r) // 2
  
    # left and right maximum_subarray_sum
    left_mss = maximum_subarray_sum_divide_conquer(arr, l, m)
    right_mss = maximum_subarray_sum_divide_conquer(arr, m+1, r)

    # Below find maximum cross the midpoint
    # 

    # Include elements on left of mid. 
    sum = left_sum = arr[m]
    start_index = m
    for i in range(m - 1, l-1, -1):
        sum = sum + arr[i] 
          
        if (sum > left_sum) : 
            left_sum = sum
            start_index = i  
    
    # Include elements on right of mid 
    sum = right_sum = arr[m + 1]
    end_index = m+1
    for i in range(m + 2, r + 1) : 
        sum = sum + arr[i] 
          
        if (sum > right_sum) : 
            right_sum = sum
            end_index = i
    
    cross_midpoint_sum = (arr[start_index:(end_index+1)], start_index, end_index, left_sum + right_sum)

    def key(e):
        return e[-1]

    # compare left, right MSS and max cross midpoint sum
    # that is the MSS of current array
    maximum = max(left_mss, right_mss, cross_midpoint_sum, key=key )

    return maximum

Description:

This algorithm using recursion, separating the array into half and half up to 1 element in its recursive loop. Then start finding the max subarray from a 2 elements array, which do comparison on left, right element and maximum of these 2 elements, then return the max back to a previous stack. So each call of the function will return the max subarry for a partial array, and so the original call will return the max subarray. Since this algorithm is using divide and conquer which break the array into half and half, it has the same size of loop as MergeSort which is log(n). Each recursive call has a loop over the entire subarray, which is O(n), so the complexity of this algorithm is O(n log n).

A Dynamic Programming solution for this problem with complexity O(n):

# usign data struct (start_index, temp_sum, max_sum)
def maximum_subarray_sum_dynamic(arr):
    n = len(arr)
    if n == 0:
        return None

    start_index = end_index = temp_start = 0
    temp_sum = max_sum = arr[0]

    # if n == 1
    # skip loop
    for i in range(1, n):
        temp_sum += arr[i]
        if temp_sum > max_sum:
            max_sum = temp_sum
            start_index = temp_start
            end_index = i

        if temp_sum < 0:
            temp_sum = 0
            temp_start = i+1
    
    return (arr[start_index:(end_index+1)], max_sum)

Description:

This algorithm only has 1 loop over elements A[1] ~ A[n-1]. Inside each loop, it keeps adding up the temporary sum. If temporary sum > max sum, then update the max sum. If the temporary sum results negative, there is no need to keep adding since adding up negative number to any number will not give us a max sum, so it will be reset to 0 in that case. Since this algorithm only has 1 loop and does constant jobs each loop, it has complexity of O(n).

Testing:

arr = [8,-1,-2,3,4,6, -5,-6,-7]

print(maximum_subarray_sum_brute_force(arr))
print(maximum_subarray_sum_divide_conquer(arr,0,len(arr)-1))
print(maximum_subarray_sum_dynamic(arr))


arr = [0, 1, -2, -3, 4, -5, 6, -7]

print(maximum_subarray_sum_brute_force(arr))
print(maximum_subarray_sum_divide_conquer(arr,0,len(arr)-1))
print(maximum_subarray_sum_dynamic(arr))


arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4, 6]

print(maximum_subarray_sum_brute_force(arr))
print(maximum_subarray_sum_divide_conquer(arr,0,len(arr)-1))
print(maximum_subarray_sum_dynamic(arr))