2873 - Maximum Value of an Ordered Triplet II (Medium)

Problem Link

https://leetcode.com/problems/maximum-value-of-an-ordered-triplet-ii

Problem Statement

You are given a 0-indexed integer array nums.

Return the maximum value over all triplets of indices $(i, j, k)$ such that $i < j < k$. If all such triplets have a negative value, return $0$.

The value of a triplet of indices $(i, j, k)$ is equal to $(nums[i] - nums[j]) * nums[k]$.

Examples

Example 1

Input:  nums = [12,6,1,2,7]
Output: 77

Explanation:

The value of the triplet (0, 2, 4) is (nums[0] - nums[2]) * nums[4] = 77. It can be shown that there are no ordered triplets of indices with a value greater than 77.

Example 2

Input: nums = [1,10,3,4,19]
Output: 133

Explanation:

The value of the triplet (1, 2, 4) is (nums[1] - nums[2]) * nums[4] = 133. It can be shown that there are no ordered triplets of indices with a value greater than 133.

Example 3

Input: nums = [1,2,3]
Output: 0

Explanation:

The only ordered triplet of indices (0, 1, 2) has a negative value of (nums[0] - nums[1]) * nums[2] = -3. Hence, the answer would be 0.

Constraints

• $3 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^6$

Approach 1: Greedy

When we are at an element $x$, we consider the candidate for different position. Let $i_{mx}$ be the maximum of $nums[i]$ and $d_{mx}$ be the maximum of the value of the diff $nums[i] - nums[j]$. At a point, we consider

• $x$ as $nums[k]$, we can maximize the answer $res$ with $d_{mx} * x$.
• $x$ as $nums[j]$, we can maximize the difference $d_{mx}$ with $i_{mx} - x$.
• $x$ as $nums[i]$, we can maximize $i_{mx}$ with $i$.

Time complexity is $O(n)$

Space comlexity is $O(1)$.

Python

Written by @wkw

# O(n)
class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        res, i_mx, d_mx = 0, 0, 0
        for x in nums:
            res = max(res, d_mx * x) # x as nums[k]
            # maximize (nums[i] - nums[j])
            d_mx = max(d_mx, i_mx - x) # x as nums[j]
            # maximize nums[i]
            i_mx = max(i_mx, x) # x as nums[i]
        return res