Maximum Subarray

Question

Given an array of integers, find the contiguous subarray within the array (containing at least one number) which has the largest sum.

Example 1

Input: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
Output: [4, -1, 2, 1] (sum = 6)

Solution

▭

all//Maximum Subarray.py

def max_subarray(arr):
    max_so_far = arr[0]
    current_max = arr[0]

    for i in range(1, len(arr)):
        current_max = max(arr[i], current_max + arr[i])
        max_so_far = max(max_so_far, current_max)

    return max_so_far

# test
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
max_subarray(arr) # 7

▯

all//Maximum Subarray.py

def max_subarray(arr):
    max_so_far = arr[0]
    current_max = arr[0]

    for i in range(1, len(arr)):
        current_max = max(arr[i], current_max + arr[i])
        max_so_far = max(max_so_far, current_max)

    return max_so_far

# test
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
max_subarray(arr) # 7