Maximum Value of an Ordered Triplet I

Leetcode Problem:

• Maximum Value of an Ordered Triplet I

Summary

• The problem requires finding the maximum value of a triplet of indices (i, j, k) in a given array such that i < j < k, and the value of the triplet is (nums[i] - nums[j]) * nums[k].

Approach

• The approach used is a recursive combination of elements from the array to form triplets, and the maximum value is updated accordingly.

Complexity

• O(n^3) due to the recursive combination of elements and the use of a vector to store selected elements.

Explanation

• The solution uses a recursive function combi() to generate all possible triplets of indices and calculate their values
• The function takes the current index, depth, and a vector of selected elements as parameters
• If the depth is 3, the function updates the maximum value if the current triplet has a greater value
• Otherwise, it recursively calls itself for the next index and increments the depth
• The function also uses backtracking to explore all possible combinations of elements by popping the last element from the vector and restoring the previous state.

Solution Code:

class Solution {
public:
    long long ans = 0;
    void combi(vector&nums, int cur, int depth, vector& selected){
        if(depth == 3){
            ans = max(ans, (selected[0] - selected[1])*selected[2]);
            return;
        }
        for(int i = cur + 1; i < nums.size(); i++){
            selected.push_back(nums[i]);
            combi(nums, i, depth + 1, selected);
            selected.pop_back();
        }
    }
    long long maximumTripletValue(vector& nums) {
        vector selected;
        combi(nums,-1, 0, selected);
        return ans;
    }
};