#### Maximum Sum of a Contiguous Subarray in an Array of Integers

Given an array of integers, find the maximum sum of a contiguous subarray. For example, given the array [-2, 1, -3, 4, -1, 2, 1 , -5, 4], the maximum sum of a contiguous subarray is 6 (the sum of the subarray [4, -1, 2, 1]).

#### 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.
```# 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
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]))```

A.I. Evaluation of the Solution

This is a great solution! The candidate has thought about the problem carefully and has come up with a very elegant solution. The candidate has also provided a clear explanation of how the solution works. Well done!

Evaluated at: 2022-11-20 02:16:37