Find Maximum Sum of Triplets in an Array in C++

Concept

With respect of a given array of positive integers of size n, our task to determine the maximum sum of triplet ( a_i + a_j + a_k ) such that 0 <= i < j < k < n and a_i< a_j< a_k.

Input

a[] = 3 6 4 2 5 10

Output

19

Explanation

All possible triplets are:-
3 4 5 => sum = 12
3 6 10 => sum = 19
3 4 10 => sum = 17
4 5 10 => sum = 19
2 5 10 => sum = 17
Maximum sum = 19

Method

Now, a simple approach is to visit for every triplet with three nested ‘for loops’ and determine update the sum of all triplets one by one. Here, time complexity of this method is O(n^3) which is not enough for higher value of ‘n’.

Again, we can apply a better approach for making further optimization in above approach. In this method, instead of visiting through every triplet with three nested loops, we can visit through two nested loops.

At the time of visiting through each number(let as middle element(a_j )), determine maximum number(a_i) less than a_j preceding it and maximum number(ak ) larger than a_j beyond it. Finally, now, update the maximum answer with calculated sum of a_i + a_j + a_k

Example

 Live Demo

// C++ program to find maximum triplet sum
#include <bits/stdc++.h>
using namespace std;
// Shows function to calculate maximum triplet sum
int maxTripletSum(int arr1[], int n1){
   // Used to initialize the answer
   int ans1 = 0;
   for (int i = 1; i < n1 - 1; ++i) {
      int max1 = 0, max2 = 0;
      // Determine maximum value(less than arr1[i])
      // from i+1 to n1-1
      for (int j = 0; j < i; ++j)
         if (arr1[j] < arr1[i])
            max1 = max(max1, arr1[j]);
      // Determine maximum value(greater than arr1[i])
      // from i+1 to n1-1
      for (int j = i + 1; j < n1; ++j)
         if (arr1[j] > arr1[i])
            max2 = max(max2, arr1[j]);
      // store maximum answer
      if(max1 && max2)
         ans1=max(ans1,max1+arr1[i]+max2);
   }
   return ans1;
}
// Driver code
int main(){
   int Arr[] = { 3, 6, 4, 2, 5, 10 };
   int N = sizeof(Arr) / sizeof(Arr[0]);
   cout << maxTripletSum(Arr, N);
   return 0;
}

Output

19