Maximum Sum of a Contiguous Subarray in an Array of Integers

Problem

Find the maximum sum of a contiguous subarray in an array of integers.
Example input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Example output: 6 (The maximum sum of a contiguous subarray is 6, which is the sum of the subarray [4, -1, 2, 1])

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.

kayakane

# Solution:
# The maximum sum of a contiguous subarray is the maximum of the sum of the subarray ending at each index.
# The sum of the subarray ending at each index is the maximum of the sum of the subarray ending at the previous index plus the value at the current index, or the value at the current index.
# The maximum sum of a contiguous subarray is the maximum of the sum of the subarray ending at each index.

def max_subarray_sum(arr):
    max_ending_here = max_so_far = arr[0]
    for x in arr[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))