Untitled

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

tuple<int, int, int> maxCrossingSubarray(int* a, int low, int mid, int high) {
    int sum = 0, leftSum = INT_MIN, leftIdx;
    for(int i = mid; i >= low; i--) {
        sum += a[i];
        if(sum > leftSum) {
            leftSum = sum;
            leftIdx = i;
        }
    }
    sum = 0;
    int rightSum = INT_MIN, rightIdx;
    for(int i = mid + 1; i <= high; i++) {
        sum += a[i];
        if(sum > rightSum) {
            rightSum = sum;
            rightIdx = i;
        }
    }
    return {leftIdx, rightIdx, leftSum + rightSum};
}

tuple<int, int, int> maxSubarray(int* a, int low, int high) {
    if(high == low) return {low, high, a[low]};
    int mid = (low + high) / 2;
    tuple<int, int, int> l, r, c;
    l = maxSubarray(a, low, mid);
    r = maxSubarray(a, mid + 1, high);
    c = maxCrossingSubarray(a, low, mid, high);
    if(get<2>(l) > get<2>(r) && get<2>(l) > get<2>(c)) return l;
    else if(get<2>(r) > get<2>(l) && get<2>(r) > get<2>(c)) return r;
    else return c; 
}

void solve(void) {
    int n; cin >> n;
    int* a = new int[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    tuple<int, int, int> ans = maxSubarray(a, 0, n - 1);
    cout << get<2>(ans) << "\n"; //Just gives the max subarray sum, modify if you want index
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}