MaxSumTriplet.cpp

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

int solve(const vector<int> &A) {
	int n = A.size();
	set<int> maxL;
    vector<int> maxR(n);
    int sum = 0, maxSum = 0;
    maxR[n - 1] = A[n - 1];
    for(int i = n - 2; i >= 0; i--) {
        maxR[i] = max(maxR[i + 1], A[i]);
    }
    maxL.insert(0);
    for(int i = 1; i < n - 1; i++) {
		maxL.insert(A[i - 1]);
		auto it = maxL.lower_bound (A[i]);
		if(maxR[i + 1] > A[i])
			sum =  *(--it) + A[i] + maxR[i + 1];
        if(sum > maxSum)
            maxSum = sum;
    }
    return maxSum;
}

int main() {
	vector<int> arr ( {18468, 6335, 26501, 19170, 15725, 11479, 29359, 26963, 24465, 5706, 28146, 23282, 16828, 9962, 492, 2996, 11943, 4828, 5437, 32392, 14605, 3903, 154, 293, 12383, 17422, 18717, 19719, 19896, 5448, 21727, 14772, 11539, 1870, 19913, 25668, 26300, 17036, 9895, 28704, 23812, 31323, 30334, 17674, 4665, 15142, 7712, 28254, 6869, 25548, 27645, 32663, 32758, 20038, 12860, 8724, 9742, 27530, 779, 12317, 3036, 22191, 1843, 289, 30107, 9041, 8943, 19265, 22649, 27447, 23806, 15891, 6730, 24371, 15351, 15007, 31102, 24394, 3549, 19630, 12624, 24085, 19955, 18757, 11841, 4967, 7377, 13932, 26309, 16945, 32440, 24627, 11324, 5538, 21539, 16119, 2083, 22930, 16542, 4834, 31116, 4640, 29659, 22705, 9931, 13978, 2307, 31674, 22387, 5022, 28746, 26925, 19073, 6271, 5830, 26778, 15574, 5098, 16513, 23987, 13291, 9162, 18637, 22356, 24768, 23656, 15575, 4032, 12053, 27351, 1151, 16942, 21725, 13967, 3431, 31108, 30192, 18008, 11338, 15458, 12288 });
	cout << solve(arr) << endl;
	return 0;
}