Maximum Value of an Ordered Triplet II

medium array prefix max

Problem

You are given an integer array nums with at least three elements. Pick any three indices i < j < k; the value of that ordered triplet is (nums[i] − nums[j]) · nums[k]. Return the largest value over all such triplets, or 0 if every triplet has a negative value.

Inputnums = [12, 6, 1, 2, 7]

Output77

Choosing i=0, j=2, k=4 gives (12 − 1) × 7 = 77, the largest value any ordered triplet can reach.

nums (comma-separated positive integers, 3 to 12 values)

def maximum_triplet_value(nums):
    ans = 0
    max_prefix = 0  # best nums[i] seen so far
    max_diff = 0    # best nums[i] - nums[j] so far
    for x in nums:
        ans = max(ans, max_diff * x)              # x plays k
        max_diff = max(max_diff, max_prefix - x)  # x plays j
        max_prefix = max(max_prefix, x)           # x plays i
    return ans

function maximumTripletValue(nums) {
  let ans = 0;
  let maxPrefix = 0; // best nums[i] seen so far
  let maxDiff = 0;   // best nums[i] - nums[j] so far
  for (const x of nums) {
    ans = Math.max(ans, maxDiff * x);           // x plays k
    maxDiff = Math.max(maxDiff, maxPrefix - x); // x plays j
    maxPrefix = Math.max(maxPrefix, x);         // x plays i
  }
  return ans;
}

long maximumTripletValue(int[] nums) {
    long ans = 0;
    long maxPrefix = 0; // best nums[i] seen so far
    long maxDiff = 0;   // best nums[i] - nums[j] so far
    for (int x : nums) {
        ans = Math.max(ans, maxDiff * x);           // x plays k
        maxDiff = Math.max(maxDiff, maxPrefix - x); // x plays j
        maxPrefix = Math.max(maxPrefix, x);         // x plays i
    }
    return ans;
}

long long maximumTripletValue(vector<int>& nums) {
    long long ans = 0;
    long long maxPrefix = 0; // best nums[i] seen so far
    long long maxDiff = 0;   // best nums[i] - nums[j] so far
    for (int x : nums) {
        ans = max(ans, maxDiff * x);           // x plays k
        maxDiff = max(maxDiff, maxPrefix - x); // x plays j
        maxPrefix = max(maxPrefix, x);         // x plays i
    }
    return ans;
}

Explanation

Trying every triplet costs O(n³), far too slow for 100,000 elements. The trick is to fix the last index k: once k is chosen, the best triplet ending there is simply (best nums[i] − nums[j] over pairs before k) × nums[k]. So if we always know the best difference to our left, every element can be judged as a final term in constant time.

That best difference, maxDiff, can itself be maintained on the fly. For a candidate middle index j, the best partner is the largest value before it, so we also keep maxPrefix, the running maximum of the prefix. When the scan reaches a value x, we update in a careful order: first use x as k (ans = max(ans, maxDiff · x)), then as j (maxDiff = max(maxDiff, maxPrefix − x)), then as a future i (maxPrefix = max(maxPrefix, x)). Updating after using guarantees the three roles always come from three distinct, increasing indices.

Walk through nums = [12, 6, 1, 2, 7]. After index 0, maxPrefix = 12. At index 1, 12 − 6 = 6 becomes the first maxDiff. At index 2 the difference improves to 12 − 1 = 11. Index 3 offers candidate 11 × 2 = 22, and index 4 offers 11 × 7 = 77 — the answer.

Initializing ans = 0 quietly handles the "all triplets negative" rule: a negative product never beats 0, so the answer simply stays 0, exactly what the problem asks us to return. Since maxPrefix and maxDiff start at 0 and values are positive, the first elements contribute harmless 0-valued candidates.

One scan with three constant-time updates per element gives O(n) time and O(1) extra space. One practical note: values reach 10⁶, so products reach 10¹², which is why the Java and C++ versions accumulate in 64-bit integers.

Time: O(n) Space: O(1)