Maximum Sum of Contiguous Subarray

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.

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;
}