Problem Informations

• Problem Index: 2873
• Problem Link: Maximum Value of an Ordered Triplet I
• Topics: Array

Problem Description

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 $(\text{nums}[i] - \text{nums}[j]) \cdot \text{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 \leq \text{nums.length} \leq 100$
• $1 \leq \text{nums}[i] \leq 10^6$

Intuition

The problem involves finding the maximum value derived from a specific operation on a triplet of indices in an array, $(i, j, k)$, with the constraint that $i < j < k$. The value is defined as $(\text{nums}[i] - \text{nums}[j]) \cdot \text{nums}[k]$. Given the constraints and the definition, we must strategically explore the possibilities of such triplets, focusing on maximizing the outcome for $(i, j, k)$. The primary challenge is efficiently calculating and updating the potential maximum triplet values without excessively iterating or recomputing.

Approach

1. Initialize Variables:

   • Start by initializing the maxTripletValue to 0, which will hold the maximum value found for any valid triplet.
   • Set maxVal as the maximum of the first two elements of nums to keep track of the largest number encountered so far.
   • Compute maxDifference as the difference between the first two numbers, nums[0] - nums[1], which assists in evaluating potential triplet calculations moving forward.

2. Iterate Over the Array:

   • Begin iterating from the third element (index 2) to the end of the array, ensuring compliance with $i < j < k$.

3. Evaluate Current Triplet Value:

   • For each element at index i, calculate the potential maximum triplet value by evaluating maxDifference * current element (i.e., nums[i]), and update maxTripletValue if this new value is larger.

4. Update Maximum Difference:

   • Continuously adjust maxDifference by comparing its current value with maxVal - current element. This step is important for preparing the calculation for the next potential triplet contribution.

5. Track Maximum Element:

   • Update maxVal to the highest value seen up to the current index. It is pivotal to ensure maxVal always contains the largest possible value from the indices used in our calculations.

6. Return the Result:

   • Once the loop concludes, the maxTripletValue will contain the maximum possible value obtained from any valid triplet. If only negative values are possible, it will remain 0, as initialized.

This approach leverages a single pass through the array to compute the desired results, ensuring the time complexity remains efficient at $O(n)$, where $n$ is the length of the input array nums.

Code

C++

class Solution {
public:
    // Helper function to return the maximum of two values
    long long max(long long a, long long b) {
        return a > b ? a : b;
    }

    // Function to find the maximum value of any triplet (i, j, k) such that i < j < k
    long long maximumTripletValue(vector<int>& nums) {
        // Initialize the maximum value of the triplet as 0
        long long maxTripletValue = 0;

        // Initialize the maximum value found so far from the first two elements
        long long maxVal = max(nums[0], nums[1]);

        // Initialize the maximum difference encountered for calculation
        long long maxDifference = nums[0] - nums[1];

        // Iterate through the array starting from the third element
        for (int i = 2; i < nums.size(); i++) {
            // Update the maximum triplet value by comparing with (maxDifference * current element)
            maxTripletValue = max(maxTripletValue, maxDifference * nums[i]);

            // Update maxDifference to hold the maximum of its current value and (maxVal - current element)
            maxDifference = max(maxDifference, maxVal - nums[i]);

            // Update maxVal to hold the maximum value of elements encountered so far
            maxVal = max(maxVal, nums[i]);
        }

        // Return the maximum value of the triplet found
        return maxTripletValue;
    }
};

Python

class Solution:
    # Helper function to return the maximum of two values
    def max(self, a: int, b: int) -> int:
        return a if a > b else b

    # Function to find the maximum value of any triplet (i, j, k) such that i < j < k
    def maximumTripletValue(self, nums: list[int]) -> int:
        # Initialize the maximum value of the triplet as 0
        maxTripletValue = 0

        # Initialize the maximum value found so far from the first two elements
        maxVal = self.max(nums[0], nums[1])

        # Initialize the maximum difference encountered for calculation
        maxDifference = nums[0] - nums[1]

        # Iterate through the array starting from the third element
        for i in range(2, len(nums)):
            # Update the maximum triplet value by comparing with (maxDifference * current element)
            maxTripletValue = self.max(maxTripletValue, maxDifference * nums[i])

            # Update maxDifference to hold the maximum of its current value and (maxVal - current element)
            maxDifference = self.max(maxDifference, maxVal - nums[i])

            # Update maxVal to hold the maximum value of elements encountered so far
            maxVal = self.max(maxVal, nums[i])

        # Return the maximum value of the triplet found
        return maxTripletValue

Complexity

• Time complexity: The time complexity of the given algorithm is $O(n)$, where $n$ is the length of the input array nums. This is because the algorithm iterates through the array once, performing constant time operations for each element.

• Space complexity: The space complexity of the algorithm is $O(1)$ since it uses only a fixed amount of additional space (namely, a few variables to store intermediate results) regardless of the input size.