Untitled
unknown
c_cpp
2 years ago
1.4 kB
11
Indexable
#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; }
Editor is loading...