Maximum Value of an Ordered Triplet I

EASY

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 (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] <= 10⁶

Approaches

Checkout 4 different approaches to solve Maximum Value of an Ordered Triplet I. Click on different approaches to view the approach and algorithm in detail.

Optimal Single Pass Linear Scan

The most optimal solution achieves both linear time and constant space complexity by processing the array in a single pass. This dynamic programming-style approach cleverly maintains the maximums needed at each step. As we iterate through the array, we consider each element as a potential nums[k], nums[j], and nums[i] in a specific order to build up the solution.

Algorithm

Initialize maxVal = 0, max_i = 0, and max_ij = 0.
max_i will track the maximum nums[i] seen so far.
max_ij will track the maximum nums[i] - nums[j] seen so far.
Iterate through each num in the nums array.
In each iteration, first update the result: maxVal = max(maxVal, (long)max_ij * num). Here, num acts as nums[k].
Then, update the maximum difference: max_ij = max(max_ij, max_i - num). Here, num acts as nums[j].
Finally, update the maximum prefix value: max_i = max(max_i, num). Here, num acts as nums[i].
Return maxVal.

We iterate through the array while maintaining two key values:

max_i: The maximum value of an element seen so far (a potential nums[i]).
max_ij: The maximum difference nums[i] - nums[j] seen so far.

For each number num in the array, we perform three updates in a specific order:

Treat num as nums[k]: We calculate a potential answer by multiplying num with the best (nums[i] - nums[j]) difference (max_ij) found among the elements before num. We update our overall maxVal with this result.
Treat num as nums[j]: We update max_ij. A new, larger difference might be formed by using num as nums[j] and the largest element seen before it (max_i) as nums[i]. So we update max_ij = max(max_ij, max_i - num).
Treat num as nums[i]: We update max_i by comparing it with the current num. This ensures max_i is ready for future elements to use as their potential nums[j] or nums[k].

The strict order of these updates is crucial for the correctness of the algorithm.

class Solution {
    public long maximumValue(int[] nums) {
        long maxVal = 0;
        int max_i = 0;
        int max_ij = 0;

        for (int num : nums) {
            // Current num is nums[k]. max_ij is max(nums[i] - nums[j]) for i < j < k.
            maxVal = Math.max(maxVal, (long)max_ij * num);

            // Current num is nums[j]. max_i is max(nums[i]) for i < j.
            max_ij = Math.max(max_ij, max_i - num);

            // Current num is nums[i]. Update max_i for future iterations.
            max_i = Math.max(max_i, num);
        }
        return maxVal;
    }
}

Complexity Analysis

Time Complexity: O(n), as we iterate through the array only once.Space Complexity: O(1), as we only use a few variables to store the running maximums.

Pros and Cons

Pros:

Most efficient solution with O(n) time and O(1) space.
Processes the array in a single pass.

Cons:

The logic can be less intuitive to grasp compared to more direct approaches.

Code Solutions

Checking out 3 solutions in different languages for Maximum Value of an Ordered Triplet I. Click on different languages to view the code.

class Solution {
public
  long maximumTripletValue(int[] nums) {
    long max, maxDiff, ans;
    max = 0;
    maxDiff = 0;
    ans = 0;
    for (int num : nums) {
      ans = Math.max(ans, num * maxDiff);
      max = Math.max(max, num);
      maxDiff = Math.max(maxDiff, max - num);
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Maximum Value of an Ordered Triplet I

Data Structures:

Array

Companies:

Media.net |