Introduction
In this blog, we will discuss how to find the maximum triplet sum in Array. Such problems do come in interviews as well as in many contests. Before solving the problem, it’s recommended to have a good understanding of sortings and greedy approaches. In this blog, we will dive deep into each detail to get a firm hold over how we can reach from a brute force solution to an optimal solution.
Problem Statement
Given an array of integers. Our task is to find the maximum triplet sum in array.
Let’s understand the problem using an example.
Sample Example
Input:
N representing the number of elements of the array, and the array Arr[].
N = 6
Arr = {2, 3, 0, -1, 8, 10}
Output:
21
Explanation:
The maximum sum can be achieved by adding the first 3 highest elements , i.e. 3 + 8 + 10 = 21Brute Force Approach
First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach. So, the basic approach is to consider each triplet in the array and choose the triplet having the maximum which be our answer.
Steps of Algorithm
So the naive/basic approach could be formulated as:
- Compute all triplet sums.
- Maximise the result while computing the triplet sums.
- Finally return the maximum triplet sum in array .
Now let’s look at the PseudoCode.
PseudoCode
___________________________________________________________________
procedure findMaximumTripletSum(arr, N):
___________________________________________________________________
1. maxTripletSum ← -∞ #initially the maximum triplet sum is -infinity.
2. for each triplet in arr do # for every triplet in the array
3. triplet_sum ← computeTripletSum(triplet) # for each triplet compute its sum
4. maxTripletSum ← max(maxTripletSum, triplet_sum) # maximise the sum
5. end for
6. return maxTripletSum # return the answer
7. end procedure
___________________________________________________________________
Implementation in C++
// program to find maximum triplet sum in array
#include <bits/stdc++.h>
using namespace std;
// function to compute the maximum triplet sum
int findMaximumTripletSum(int n, int arr[]){
int maximumTripletSum = INT_MIN; // variable to store the answer
if(n<=2) return maximumTripletSum;
// compute the sum for each triplet(arr[i], arr[j], arr[k])
// and maximise the result
for(int i=0;i<n-2;++i){
for(int j=i+1; j<n-1; ++j){
for(int k=j+1; k<n; ++ k){
int triplet_sum = arr[i]+arr[j]+arr[k];
maximumTripletSum = max(maximumTripletSum, triplet_sum);
}
}
}
return maximumTripletSum; // return the result;
}
int main() {
// initialise the input parameters here
int n = 6; // store the size of the array
int arr[] = {2, 3, 0, -1, 8, 10}; // store the array
// compute the maximum triplet sum in array
int maximumTripletSum = findMaximumTripletSum(n, arr);
// print the answer
cout<<"The maximum triplet sum in array is: "<<maximumTripletSum;
return 0;
}
Output:
The maximum triplet sum in array is: 21
Complexity Analysis
Time Complexity: O(n3)
This is because we iterate through all triplets in the array. Hence it’s O(n3).
Space complexity: O(1) at the worst case because no extra space is used.
The above algorithm works in O(n3) time which is pretty slow. This gives us the motivation to improve our algorithm.
So let’s think about an efficient approach to solve the problem.
569+ registered 
