Maximum Value of an Ordered Triplet I Solution in C++

Explore Solutions in Other Languages

Problem Description

Ah, the classic “Maximum Value of an Ordered Triplet” problem! You have an array of integers, and your mission is to find three indices i, j, and k such that i < j < k and maximize the expression nums[i] - nums[j] + nums[k].

In real life, think of it as trying to maximize your savings while shopping. You want to buy a fancy gadget (nums[k]), but you also want to make sure you don’t overspend (nums[j]) while still getting the best deal (nums[i]).

Code Solution


class Solution {
 public:
  long long maximumTripletValue(vector& nums) {
    long ans = 0;
    int maxDiff = 0;  // max(nums[i] - nums[j])
    int maxNum = 0;   // max(nums[i])

    for (const int num : nums) {
      ans = max(ans, static_cast(maxDiff) * num);  // num := nums[k]
      maxDiff = max(maxDiff, maxNum - num);              // num := nums[j]
      maxNum = max(maxNum, num);                         // num := nums[i]
    }

    return ans;
  }
};

Approach

The approach here is to iterate through the array while keeping track of the maximum difference between the first and second elements (maxDiff) and the maximum value of the first element (maxNum). For each element, we calculate the potential maximum triplet value and update our answer accordingly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n) – We traverse the array once.
Space Complexity	O(1) – We use a constant amount of space.

Real-World Example

Imagine you’re at a flea market. You spot a vintage record player (nums[k]) that you absolutely must have. However, you also remember that you need to haggle down the price of a record (nums[j]) you want to buy, while also ensuring you don’t overspend on a fancy vinyl (nums[i]). The goal is to maximize your overall satisfaction while minimizing your expenses.