Find maximum sum of triplets in an array such than i < j < k and a[i] < a[j] < a[k]

https://www.geeksforgeeks.org/find-maximum-sum-triplets-array-j-k-ai-aj-ak/

Given an array of positive integers of size n. Find the maximum sum of triplet( ai + aj + ak ) such that 0 <= i < j < k < n and ai < aj < ak.

Input: a[] = 2 5 3 1 4 9
Output: 16

Explanation:
All possible triplets are:-
2 3 4 => sum = 9
2 5 9 => sum = 16
2 3 9 => sum = 14
3 4 9 => sum = 16
1 4 9 => sum = 14
Maximum sum = 16

Best and efficient approach is use the concept of maximum suffix-array and binary search.

• For finding maximum number greater number greater than given number beyond it, we can maintain a maximum suffix-array array such that for any number(suffixi) it would contain maximum number from index i, i+1, … n-1. Suffix array can be calculated in O(n) time.
• For finding maximum number smaller than the given number preceding it, we can maintain a sorted list of numbers before a given number such we can simply perform a binary search to find a number which is just smaller than the given number. In C++ language, we can perform this by using set associative container of STL library.

Time complexity: O(n*log(n))

int maxTripletSum(int arr[], int n)

{

    // Initialize suffix-array

    int maxSuffArr[n + 1];

  

    // Set the last element

    maxSuffArr[n] = 0;

  

    // Calculate suffix-array containing maximum

    // value for index i, i+1, i+2, ... n-1 in

    // arr[i]

    for (int i = n - 1; i >= 0; --i)

        maxSuffArr[i] = max(maxSuffArr[i + 1], arr[i]);

  

    int ans = 0;

  

    // Initialize set container

    set<int> lowValue;

  

    // Insert minimum value for first comparison

    // in the set

    lowValue.insert(INT_MIN);

  

    for (int i = 0; i < n - 1; ++i) {

        if (maxSuffArr[i + 1] > arr[i]) {

            ans = max(ans, getLowValue(lowValue,

                                       arr[i])

                               + arr[i] + maxSuffArr[i + 1]);

  

            // Insert arr[i] in set<> for further

            // processing

            lowValue.insert(arr[i]);

        }

    }

    return ans;

}




Simple Approach is to traverse for every triplet with three nested ‘for loops’ and find update the sum of all triplets one by one. Time complexity of this approach is O(n3) which is not sufficient for larger value of ‘n’.

Better approach is to make further optimization in above approach. Instead of traversing through every triplets with three nested loops, we can traverse through two nested loops. While traversing through each number(assume as middle element(aj)), find maximum number(ai) smaller than aj preceding it and maximum number(ak) greater than aj beyond it. Now after that, update the maximum answer with calculated sum of ai + aj + ak

    static int maxTripletSum(int arr[], int n)

    {

        // Initialize the answer

        int ans = 0;

  

        for (int i = 1; i < n - 1; ++i) {

            int max1 = 0, max2 = 0;

  

            // find maximum value(less than arr[i])

            // from i+1 to n-1

            for (int j = 0; j < i; ++j)

                if (arr[j] < arr[i])

                    max1 = Math.max(max1, arr[j]);

  

            // find maximum value(greater than arr[i])

            // from i+1 to n-1

            for (int j = i + 1; j < n; ++j)

                if (arr[j] > arr[i])

                    max2 = Math.max(max2, arr[j]);

  

            // store maximum answer

            ans = Math.max(ans, max1 + arr[i] + max2);

        }

  

        return ans;

    }