Maximum Value of an Ordered Triplet I and II | Leetcode 2874 | Leetcode 2873

class Solution {
    #define ll long long
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n =  nums.size();
        //Step-1: Find right_max for all indices
        vector<int> right_max(n);
        int max_val = nums[n-1];//last element
        for(int i=n-2;i>0;--i){
            right_max[i] = max_val;
            max_val = max(max_val,nums[i]);
        }

        //Step-2: Find max_triplet
        ll max_triplet = 0;
        max_val = nums[0];
        for(int i=1;i<n-1;++i){
            max_triplet = max<ll>(max_triplet,(1LL*max_val-nums[i])*right_max[i]);
            max_val = max(max_val,nums[i]);
        }
        return max_triplet;
    }
};

class Solution {
    #define ll long long
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n=nums.size();
        ll max_diff = 0;
        ll max_left = 0;
        ll max_triplet = 0;
        for(int i=0;i<n;++i){
            max_triplet = max<ll>(max_triplet,1LL*max_diff*nums[i]);
            max_diff = max<ll>(max_diff,(max_left-nums[i]));
            max_left = max<ll>(max_left,nums[i]);
        }
        return max_triplet;
    }
};

/*
//JAVA
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        // Step-1: Find right_max for all indices
        int[] rightMax = new int[n];
        int maxVal = nums[n - 1]; // last element
        for (int i = n - 2; i > 0; --i) {
            rightMax[i] = maxVal;
            maxVal = Math.max(maxVal, nums[i]);
        }

        // Step-2: Find max_triplet
        long maxTriplet = 0;
        maxVal = nums[0];
        for (int i = 1; i < n - 1; ++i) {
            maxTriplet = Math.max(maxTriplet, (long)(maxVal - nums[i]) * rightMax[i]);
            maxVal = Math.max(maxVal, nums[i]);
        }
        return maxTriplet;
    }
}

// Alternative Java Solution (Optimized Space)
class Solution {
    public long maximumTripletValue(int[] nums) {
        int n = nums.length;
        long maxDiff = 0;
        long maxLeft = 0;
        long maxVal = 0;
        for (int i = 0; i < n; ++i) {
            maxVal = Math.max(maxVal, maxDiff * nums[i]);
            maxDiff = Math.max(maxDiff, maxLeft - nums[i]);
            maxLeft = Math.max(maxLeft, nums[i]);
        }
        return maxVal;
    }
}

#Python
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        n = len(nums)
        # Step-1: Find right_max for all indices
        right_max = [0] * n
        max_val = nums[-1]  # last element
        for i in range(n - 2, 0, -1):
            right_max[i] = max_val
            max_val = max(max_val, nums[i])
        
        # Step-2: Find max_triplet
        max_triplet = 0
        max_val = nums[0]
        for i in range(1, n - 1):
            max_triplet = max(max_triplet, (max_val - nums[i]) * right_max[i])
            max_val = max(max_val, nums[i])
        return max_triplet

# Alternative Python Solution (Optimized Space)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        max_diff = 0
        max_left = 0
        max_val = 0
        for num in nums:
            max_val = max(max_val, max_diff * num)
            max_diff = max(max_diff, max_left - num)
            max_left = max(max_left, num)
        return max_val
*/