Coding interview Essentials

40. Max triplet sum

Max triplet sum

Introduction

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;
}