Maximum Value of an Ordered Triplet II - Video Solutions

Problem Overview: You are given an integer array nums. Choose indices i < j < k that maximize the expression (nums[i] - nums[j]) * nums[k]. If every combination produces a negative value, the result should be 0. The challenge is respecting the index order while searching for the largest possible product.

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

The most direct method checks every valid triplet. Use three nested loops: the first picks i, the second picks j where j > i, and the third picks k where k > j. For each combination compute (nums[i] - nums[j]) * nums[k] and keep the maximum value encountered. This guarantees correctness because every ordered triplet is evaluated. The downside is performance: the algorithm performs roughly n^3 operations, which becomes impractical once the array grows beyond a few hundred elements.

Approach 2: Prefix Maximum + Best Difference Tracking (O(n) time, O(1) space)

The expression can be rearranged conceptually into two parts: first maximize (nums[i] - nums[j]) for i < j, then multiply it with nums[k] where k > j. While scanning the array, maintain the largest value seen so far for nums[i]. For each potential middle index j, compute the difference maxPrefix - nums[j]. Track the best difference encountered so far because any future k can use it. When visiting a new index as k, multiply nums[k] with the stored maximum difference and update the answer. This transforms the search from three nested loops into a single linear pass using constant extra memory.

This strategy relies on maintaining prefix information, a common pattern in array problems. By compressing earlier choices into running values (maxPrefix and maxDiff), the algorithm avoids recomputation and achieves linear time. The technique is closely related to prefix techniques and greedy-style updates often used in high‑performance greedy scans.

Recommended for interviews: The linear scan with prefix tracking is the expected solution. Interviewers want to see that you recognize how to separate the triplet expression into reusable intermediate values. Mentioning the brute force solution first demonstrates understanding of the constraints, but deriving the O(n) approach shows stronger algorithmic reasoning.