Maximum Value of an Ordered Triplet I - Video Solutions

Problem Overview: You are given an integer array nums. The goal is to compute the maximum value of the expression (nums[i] - nums[j]) * nums[k] such that i < j < k. If every possible value is negative, return 0. The challenge is efficiently evaluating valid triplets while respecting the index ordering constraint.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

The most direct method checks every ordered triplet (i, j, k) where i < j < k. Use three nested loops: the outer loop selects i, the second selects j, and the third selects k. For each combination, compute (nums[i] - nums[j]) * nums[k] and track the maximum value seen. This approach is useful for verifying correctness and understanding the problem constraints, but it quickly becomes impractical because the number of triplets grows cubically. With arrays of size n, the runtime is O(n^3) and the algorithm uses constant extra memory O(1). This method works only for very small inputs.

Approach 2: Prefix and Suffix Maximums (O(n) time, O(n) space)

The expression (nums[i] - nums[j]) * nums[k] can be maximized by selecting the largest possible nums[i] before j and the largest possible nums[k] after j. Instead of enumerating every triplet, precompute helpful values. First build a prefix array where prefixMax[j] stores the maximum element from index 0 to j. Then build a suffix array where suffixMax[j] stores the maximum element from index j to the end of the array.

Now treat each index j as the middle element of the triplet. The best candidate on the left is prefixMax[j-1], and the best candidate on the right is suffixMax[j+1]. Compute the value (prefixMax[j-1] - nums[j]) * suffixMax[j+1] and update the global maximum. This reduces the search from three nested loops to a single pass over the array after preprocessing. The overall complexity becomes O(n) time with O(n) extra memory.

This technique works because the best triplet for a fixed j must use the maximum available value on both sides to maximize the difference and the multiplier. Precomputing those values avoids repeated scanning of the array.

The solution relies on simple preprocessing over an array and a classic prefix/suffix preprocessing pattern often used in problems involving range maximum queries. Variants of this idea appear frequently in optimization problems where each index acts as a pivot.

Recommended for interviews: The prefix and suffix maximum approach. Interviewers expect candidates to move beyond brute force and recognize that the optimal i and k for each j are simply the maximum values on each side. Implementing this in O(n) time shows strong problem‑decomposition skills while keeping the code straightforward.