Maximum Value of an Ordered Triplet II

Leetcode Problem:

• Maximum Value of an Ordered Triplet II

Summary

• Find the maximum value over all triplets of indices (i, j, k) such that i < j < k in the given array nums.

Approach

• The approach used is to use a stack to store the elements of the array
• We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
• We also update the maximum value by multiplying the maximum distance with the current element
• If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
• Finally, we return the maximum value found.

Complexity

• O(n log n) due to the sorting operation inside the while loop

Explanation

• The solution code uses a stack to store the elements of the array
• We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
• We also update the maximum value by multiplying the maximum distance with the current element
• If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
• This is done to ensure that the stack always contains the smallest and largest elements seen so far
• Finally, we return the maximum value found.

Solution Code:

class Solution {
public:

    long long maximumTripletValue(vector& nums) {
        long long ans = 0;
        int maxDist = 0;
        vector st;

        for(int i = 0; i < nums.size(); i++){
            if(st.size() >= 2){
                maxDist = max(maxDist, st[0] - st.back());
            }
            ans = max(ans, (long long)maxDist * nums[i]);
            while(!st.empty() && st.back() < nums[i]){
                st.pop_back();
            }
            st.push_back(nums[i]);
        }
        return ans;
    }
};