Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
PseudoCode
2.3.
Implementation in C++
2.3.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
PseudoCode
3.3.
Implementation in C++
3.3.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
Does a greedy algorithm always work?
4.2.
Why is sorting important?
4.3.
Is Merge Sort a stable sorting algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024

Maximum triplet sum in Array

Author aniket verma
1 upvote

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 = 21

Brute 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:

  1. Compute all triplet sums.
  2. Maximise the result while computing the triplet sums.
  3. 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

7end 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing.

So the redundancy in our above approach is that we are computing the sum of all triplets and at each point we are maximizing the result. But if we carefully look at the task, we are just asked to return the sum of first 3 highest elements.

So we just need to sort the array and the last 3 elements would be the first 3 highest elements and their sum will be the maximum triplet sum.

But do we really need to sort the array? Can we find the first 3 highest elements without sorting the elements of the array? Just picking out first 3 highest elements would do so we can find them iteratively by first finding the maximum element, then the second maximum element and finally the third maximum element.

Following this approach will definitely improve the efficiency of the algorithm, because we don’t require any redundant computations.  

Steps of Algorithm

Now we can formulate our approach:

  1. Compute the first maximum element.
  2. Compute the second highest element.
  3. Compute the third highest element.
  4. Return their sum.    

 

Let’s look at the pseudoCode

PseudoCode

___________________________________________________________________

procedure findMaximumTripletSum(arr, N):

___________________________________________________________________

1.    maxTripletSum ← -∞ #initially the maximum triplet sum is -infinity.

2.    firstMaximumIndex, secondMaximumIndex, thirdMaximumIndex  ← 0, 0, 0 

3.    Compute the top 3 highest element indices in the array 

4.    maxTripletSum ← arr[firstMaximumIndex] + arr[ secondMaximumIndex] + 

     arr[ thirdMaximumIndex]  # maximise the sum   

5.  return maxTripletSum # return the answer

6end procedure

___________________________________________________________________

Implementation in C++

//C++ program to find the 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;


    // store the indices of top 3 highest elements.    
    int firstMaximumIndex = 0;
    int secondMaximumIndex = 0;
    int thirdMaximumIndex = 0;
    
    // compute the first maximum
    for(int i=0;i<n;++i){
        if(arr[i]>=arr[firstMaximumIndex]){
            firstMaximumIndex = i;
        }
    }
    
    // compute the second maximum
    for(int i=0;i<n;++i){
        if(arr[i]>=arr[secondMaximumIndex] and 
            i != firstMaximumIndex and
            arr[i]<=arr[firstMaximumIndex]){
            secondMaximumIndex = i;
        }
    }
    
    // compute the third maximum
    for(int i=0;i<n;++i){
        if(arr[i]>=arr[thirdMaximumIndex] and 
            i != secondMaximumIndex and
            i != firstMaximumIndex and 
            arr[i]<=arr[secondMaximumIndex]){
            thirdMaximumIndex = i;
        }
    }
    
    // update the maximumTripletSum
    maximumTripletSum = arr[firstMaximumIndex] + arr[secondMaximumIndex] + arr[thirdMaximumIndex];
    
    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(n)

Since we are computing maximums in all the 3 iterations over the array and it will take 3 traversals over the array to compute the result.

Space complexity: O(1) at the worst case, as we are not using any auxiliary space. 

 

Hence we reached an efficient solution from a cubic solution. But we could also compute the result in a single traversal as well and is left as an exercise!!!! 

Also see,  Rabin Karp Algorithm

Frequently Asked Questions

Does a greedy algorithm always work?

No, a greedy algorithm does not work every time. To solve a problem via a greedy algorithm, you need to have proof in your mind so as to why your solution/algorithm should work.

Why is sorting important?

Sorting is a very useful technique because we can reduce a significant number of comparisons. 

Is Merge Sort a stable sorting algorithm?

Yes, MergeSort is a stable sorting algorithm.

Conclusion

This article taught us how to solve the problem of finding the maximum triplet sum in array. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

Recommended problems -

 

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!

Previous article
Book Allocation Problem
Next article
Search an element in an array where difference between adjacent elements is 1
Live masterclass