Problem: Maximum sum triplet

Statement:

Given an array A containing N integers.

You need to find the maximum sum of triplet ( Ai + Aj + Ak ) such that 0 <= i < j < k < N and Ai < Aj < Ak.

If no such triplet exists return 0.

Solution:

1. One solution can be to run 3 nested for loops and find the max triplet sum. Time complexity and space complexity will be O(N³) and O(1) respectively.
2. Another solution can be to pick every element and consider it as the middle element of the triplet. And find the max element to the left of t and right of it. Here, Time complexity and space complexity will be O(N²) and O(1) respectively.
3. But there is the best solution to this problem which goes like this with time complexity of O(N log N) and space complexity of O(N). Pick every element one by one and consider it as the centre of the triplet and in order to find the max element to the right of it just use the suffix max element calculation and store it in an array. And then in order to find the max element to the left use a set to find the element in time complexity of O(log N). So, the overall time complexity is O(NlogN).

Pseudocode:

Hope it was helpful!