Maximum Value of an Ordered Triplet I

Medium
712.

Maximum Value of an Ordered Triplet I

Maximum Value of an Ordered Triplet I is a medium coding problem on arrays, math and prefix sum, asked in Amazon, Google and Uber interviews.

The value of an ordered triplet (i, j, k) with i < j < k is (nums[i] - nums[j]) * nums[k].

Return the maximum value over all such triplets, or 0 if every triplet has a negative value.

Example 1

Input
nums = [12,6,1,2,7]
Output
77
Explanation
(12 - 1) * 7 = 77.

Example 2

Input
nums = [1,10,3,4,19]
Output
133
Explanation
(1 - 10) is negative; (10 - 3) * 19 = 133.

Example 3

Input
nums = [1,2,3]
Output
0
Explanation
The only triplet gives (1 - 2) * 3 = -3, so the answer floors at 0.

Constraints

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumTripletValue = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Value of an Ordered Triplet I — Problem & Solution

Maximum Value of an Ordered Triplet I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Value of an Ordered Triplet I is a medium coding problem on arrays, math and prefix sum, asked in Amazon, Google and Uber interviews.

  • Difficulty: Medium
  • Topics: Arrays, Math, Prefix Sum
  • Asked at: Amazon, Google, Uber
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The value of an ordered triplet (i, j, k) with i < j < k is (nums[i] - nums[j]) * nums[k].

Return the maximum value over all such triplets, or 0 if every triplet has a negative value.

Example 1

Input: nums = [12,6,1,2,7]
Output: 77
Explanation: (12 - 1) * 7 = 77.

Example 2

Input: nums = [1,10,3,4,19]
Output: 133
Explanation: (1 - 10) is negative; (10 - 3) * 19 = 133.

Example 3

Input: nums = [1,2,3]
Output: 0
Explanation: The only triplet gives (1 - 2) * 3 = -3, so the answer floors at 0.

Constraints

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000000

Hints for Maximum Value of an Ordered Triplet I

  1. Hint 1

    The brute force is O(n³). Think about what each index needs to know about the ones before it.

  2. Hint 2

    For a fixed k, you want the largest nums[i] - nums[j] with i < j < k.

  3. Hint 3

    Sweep once, carrying the best nums[i] so far and the best difference so far.

How to solve Maximum Value of an Ordered Triplet I

Sweep k from left to right while maintaining two running maxima: the largest element seen so far, and the largest difference nums[i] - nums[j] over pairs entirely before k. Then each k is answered in constant time.

Approach

  1. Keep bestI (the maximum element seen), bestDiff (the maximum nums[i] - nums[j] with i < j), and best (the answer, starting at 0).
  2. At index k, first update best with bestDiff * nums[k].
  3. Then update bestDiff with bestI - nums[k], and finally bestI with nums[k].

Why it works

The update order is what enforces i < j < k: bestDiff is read before it is allowed to include index k as a j, and bestI is updated last so it never contributes an i at or after the j that uses it.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Updating bestI before bestDiff lets i and j be the same index.
  • Updating bestDiff before reading it lets j equal k.
  • The answer floors at 0, so it must start at 0 rather than at negative infinity.

Reference solution

Python

from typing import List

def maximumTripletValue(nums: List[int]) -> int:
    best = best_diff = best_i = 0
    for x in nums:
        best = max(best, best_diff * x)
        best_diff = max(best_diff, best_i - x)
        best_i = max(best_i, x)
    return best

Java

public static int maximumTripletValue(int[] nums) {
    long best = 0, bestDiff = 0, bestI = 0;
    for (int x : nums) {
        best = Math.max(best, bestDiff * x);
        bestDiff = Math.max(bestDiff, bestI - x);
        bestI = Math.max(bestI, x);
    }
    return (int) best;
}

C++

int maximumTripletValue(vector<int>& nums) {
    long long best = 0, bestDiff = 0, bestI = 0;
    for (int x : nums) {
        best = max(best, bestDiff * x);
        bestDiff = max(bestDiff, bestI - x);
        bestI = max(bestI, (long long) x);
    }
    return (int) best;
}

JavaScript

var maximumTripletValue = function(nums) {
    var best = 0, bestDiff = 0, bestI = 0;
    for (var k = 0; k < nums.length; k++) {
        if (bestDiff * nums[k] > best) best = bestDiff * nums[k];
        if (bestI - nums[k] > bestDiff) bestDiff = bestI - nums[k];
        if (nums[k] > bestI) bestI = nums[k];
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum