02_Maximum_Value_of_an_Ordered_Triplet_I.cpp

// 2873. Maximum Value of an Ordered Triplet I

// You are given a 0-indexed integer array nums.

// Return the maximum value over all triplets of indices (i, j, k) such that i < j < k. If all such triplets have a negative value, return 0.

// The value of a triplet of indices (i, j, k) is equal to (nums[i] - nums[j]) * nums[k].

// Example 1:

// Input: nums = [12,6,1,2,7]
// Output: 77
// Explanation: The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77.
// It can be shown that there are no ordered triplets of indices with a value greater than 77.
// Example 2:

// Input: nums = [1,10,3,4,19]
// Output: 133
// Explanation: The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133.
// It can be shown that there are no ordered triplets of indices with a value greater than 133.
// Example 3:

// Input: nums = [1,2,3]
// Output: 0
// Explanation: The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

// Constraints:

// 3 <= nums.length <= 100
// 1 <= nums[i] <= 106

class Solution
{
public:
    long long maximumTripletValue(vector<int> &nums)
    {
        long maxi = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int k = nums.size() - 1; k > i; k--)
            {
                int j = i + 1;
                while (j < k)
                {
                    maxi = max(maxi, (long(nums[i] - nums[j]) * nums[k]));
                    j++;
                }
            }
        }
        return maxi < 0 ? 0 : maxi;
    }
};

/*
This code finds the maximum value possible from triplets (i,j,k) where i < j < k using the formula (nums[i] - nums[j]) * nums[k].

The approach:
1. Uses three nested loops to try all possible combinations of i, j, k indices
2. Outer loop (i) starts from beginning
3. Middle loop (k) starts from end and moves backwards
4. Inner loop (j) tries all values between i and k
5. For each combination, calculates value and keeps track of maximum
6. Returns 0 if maximum is negative, else returns maximum value

Time Complexity: O(n^3) where n is length of array
Space Complexity: O(1) as only using constant extra space
*/