//Kadanes Algo
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> arr = {-2,1,-3,4,-1,2,1,-5,4};

    int curr = arr[0];
    int maxSum = arr[0];

    for (int i = 1; i < arr.size(); i++) {
        curr = max(arr[i], curr + arr[i]);
        maxSum = max(maxSum, curr);
    }

    cout << "Maximum Subarray Sum: " << maxSum << endl;
}