# Max triplet sum

## Problem statement

[example:max_triplet:exercice1] Write a function that, given an array $$I$$ of length $$n$$, returns the maximum value obtainable by summing $$3$$ distinct elements of $$I$$: $$I_i$$, $$I_j$$ and $$I_k$$ such that $$0 \leq i < j < k \leq n-1$$ and $$I_i < I_j < I_k$$.

[example:max_triplet:example1]
Given $$I = \{2, 5, 3, 1, 4, 9\}$$ the function returns $$16$$. The max value of $$16$$ is obtainable by summing together the elements of $$I$$ at indices: $$0$$,$$1$$ and $$5$$ : $$I_0 + I_1+I_5=2+5+9= 16$$.

Notice that there is another way of obtains the max sum of $$16$$, that is by using the elements at indices $$2$$,$$4$$ and $$5$$: $$I_2 + I_4+I_5=3+4+9= 16$$.

[example:max_triplet:example2]
Given $$I = \{3,2,1\}$$ the function returns $$-1$$ as there is no valid triplet in $$I$$.

Given $$I = \{1,3,2\}$$ the function returns $$-1$$ as there is no valid triplet in $$I$$. [ex:max_triplet:example2]

Given $$I = \{1,2,3\}$$ the function returns $$6$$. There is only one valid triplet in $$I$$. [ex:max_triplet:example3]

## Clarification Questions

Is it guaranteed that $$I$$ contains at least three elements?

No. When $$n < 3$$ the function should return $$-1$$.

Is it guaranteed the answer to fit a standard ?

Yes you can assume the the answer always fits a standard $$4$$-bytes

## Discussion

The problem is asking us to find the largest possible sum obtainable by summing up three distinct elements of $$I$$ with the additional constraint that when ordered according to their indices they form a sorted sequence. You can form such a triplet by selecting an element at index $$i$$, then another element at index $$j$$ that it appears after and it is larger than the element at position $$i$$ and finally, a third element at index $$k$$ which appears after and it is larger than the element at index $$j$$.

## Brute-force

We can solve this problem trivially in a brute-force manner by trying all possible triplets of ordered indices $$i < j <k$$ and keep track of the triplet yielding the maximum value. Three simple nested loops are enough to implement this idea, as shown in Listing [list:max_triplet_bruteforce]. The time complexity of this approach is $$(O(|I|^3)$$ which is far from being optimal. The space complexity is $$O(1)$$ as no additional space is used.

Listing 1: Cubic time complexity bruteforce solution.

int max_triplet_sum_bruteforce(const std::vector<int>& I)
{
const auto n = std::ssize(I);
int ans      = -1;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (!(I[i] < I[j]))
continue;

for (int k = j + 1; k < n; k++)
{
if (!(I[j] < I[k]))
continue;
// here: i < j < k and I[i] < I[j] < I[k]
ans = std::max(ans, I[i] + I[j] + I[k]);
}
}
}
return ans;
}

The cubic time complexity approach discussed in Section 44.4 can be dramatically improved if we approach the problem a little differently. Imagine we would be able to efficiently calculate $$L_j$$ and $$G_j$$ for an element at index $$j$$ where:

1. $$L_j$$ is the largest value among any of the elements of $$I$$ appearing at any index smaller than $$j$$ and it is smaller than $$I_j$$;

2. $$G_j$$ is the largest value among any of the elements of $$I$$ appearing at any index higher than $$j$$ and it is larger than $$I_J$$.

When these values are available we can calculate the value of the largest sum obtainable by any triplet having $$I_j$$ as the middle element. The triplet $$(L_j, I_j, G_j)$$ yield the largest sum as if that was not the case it would mean that either existed a larger element than $$L_j$$ that is smaller than $$I_j$$ in any of the positions before $$j$$ or that existed an element that is larger than $$G_j$$ in any of the positions after $$j$$. Both of these two scenarios are impossible because $$L_j$$ is by definition the largest element that is smaller than $$I_j$$ and appears before index $$j$$ and similarly, $$G_j$$ is defined to be the largest element appearing after index $$j$$ and that is larger than $$I_j$$.

We can use this fact to calculate the answer to this problem by looping over $$I$$ and for each element $$I_j$$ calculate $$L_j+ I_j+ G_j$$. The largest of the sums calculated this way is the final answer. But how can we calculate $$L_j$$ and $$G_j$$ for $$I_j$$?

$$L_j$$ can be calculated efficiently by keeping a sorted list of all the values appearing before index $$j$$ and use binary search to find $$L_j$$ in the list while $$G_j$$ can be precalculated in a similar fashion to what we have done for the problem in Chapter 6 where we loop from the right to the left of $$I$$ and we keep track of the largest element ($$M$$) seen so far. If $$M$$ is larger then the element we are currently examining ($$I_x$$) then $$M$$ is also the largest element larger than $$I_x$$ appearing after $$x$$. If not, it means that $$I_x$$ is the largest element so far, and that $$I_x$$ does not have any larger element on its right: thus $$M = I_x$$ (see Section 6.3.2 and Listing [list:greatest_right_final1]).

Listing 2: $O(nlog(n))$ solution to the max triplet sum problem.

constexpr auto MIN_INT = std::numeric_limits<int>::min();
auto find_largest_smaller_than(const std::set<int>& N, const int n)
{
auto it = N.lower_bound(n);
if (N.size() == 0 || it == std::begin(N))
return std::make_tuple(MIN_INT, false);
return std::make_tuple(*(--it), true);
}

int max_triplet_sum_prefix_binary_search(const vector<int>& A)
{
std::set<int> N;
std::vector<int> L;

L.resize(A.size(), MIN_INT);
int M = A[A.size() - 1];
for (int i = std::ssize(A) - 2; i >= 0; i--)
{
L[i] = A[i] < M ? M : MIN_INT;
M    = std::max(A[i], M);
}

int ans = -1;
for (size_t i = 0; i < A.size(); i++)
{
auto larger            = L[i];
auto [smaller, exists] = find_largest_smaller_than(N, A[i]);
if (larger != MIN_INT && exists)
ans = std::max(ans, A[i] + larger + smaller);
N.insert(A[i]);
}
return ans;
}