Largest Sum Contiguous Subarray

 

#include <iostream>
#include <vector>
using namespace std;


int partial_sum(vector<int>& sum, int x, int y) {
    return sum[y] - sum[x - 1];
}

void sum_array(vector<int>& v, vector<int>& sum) {
    sum.push_back(v[0]);
    for (auto i = 1; i < v.size(); i++) {
        sum.push_back(sum[i - 1] + v[i]);
    }
}

int max_sum_subarray(vector<int>& sum) {
    int minSum = 0;
    int result = INT_MIN;
    for (int r = 0; r < sum.size(); r++) {
        if (sum[r] - minSum > result) {
            result = sum[r] - minSum;
        }
        if (sum[r] < minSum) {
            minSum = sum[r];
        }
    }
    return result;
}

int main()
{
    vector<int> v = { -2, -3, 4, -1, -2, 1, 5, -3 };
    vector <int> sum;
    sum_array(v, sum);
    cout << max_sum_subarray(sum);
    return 0;
}