Maximum Subarray Sum

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Example:

Input:  n = 8, arr = {-1, 3, -2, 5, 3, -5, 2, 2}
Output: 9

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9;

void maximumSubarraySum(long long n,
                        vector<long long> &arr)
{

    long long ans = -INF, cur = -INF;
    for (long long i = 0; i < n; i++)
    {
        long long x = arr[i];
        cur = max(x, cur + x);
        ans = max(ans, cur);
    }
    cout << ans << "\n";
}

int main()
{

    long long n = 8;

    vector<long long> arr = {-1, 3, -2, 5, 3, -5, 2, 2};

    maximumSubarraySum(n, arr);

    return 0;
}