#### Maximum Sum of Contiguous Subarray

Given an array of n integers, this algorithm finds the maximum sum of any contiguous subarray of the array in O(n) time.

#### Problem

```Given an array of n integers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since we would take the subarray [42, 14, -5, 86].
Given the array [-5, -1, -8, -9], the maximum sum would be 0, since we would take the subarray [-1, -8, -9].
Do this in O(n) time.```

#### Solution

This solution is in C++. Our A.I. can create solutions in multiple languages.
by kayakane
```#include <iostream>
#include <vector>

using namespace std;

int max_sum(vector<int>& arr) {
int max_sum = 0;
int curr_sum = 0;
for (int i = 0; i < arr.size(); i++) {
curr_sum += arr[i];
if (curr_sum < 0) {
curr_sum = 0;
}
if (curr_sum > max_sum) {
max_sum = curr_sum;
}
}
return max_sum;
}

int main() {
vector<int> arr = {34, -50, 42, 14, -5, 86};
cout << max_sum(arr) << endl;
return 0;
}```

A.I. Evaluation of the Solution

The candidate's solution correctly solves the problem and runs in O(n) time. The approach is generally sound, though there is room for improvement in terms of code clarity. In particular, the variable names could be more descriptive and the use of a single loop could be more clearly explained. Overall, though, this is a solid solution.

Evaluated at: 2022-11-22 10:16:10