Find the Maximum Sum of a Contiguous Subarray

Given an array of n integers, this algorithm will find the maximum sum of any contiguous subarray of the array. For example, given the input array [1, -3, 2, 1, -1], the algorithm would output 3.

Problem

Given an array of n integers, find the maximum sum of any contiguous subarray of the array.
Example input: [1, -3, 2, 1, -1]
Example output: 3

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.
by kayakane
def max_subarray(arr):
    max_sum = 0
    current_sum = 0
    for i in range(len(arr)):
        current_sum += arr[i]
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < 0:
            current_sum = 0
    return max_sum

print(max_subarray([1, -3, 2, 1, -1]))

A.I. Evaluation of the Solution

The candidate's solution correctly finds the maximum sum of any contiguous subarray of the given array. The approach is to keep track of the current sum as we iterate through the array, and update the maximum sum if necessary. If the current sum ever becomes negative, we reset it to 0 since we know that a subarray with a negative sum will never be the maximum sum.

Evaluated at: 2022-12-09 00:15:39