What is the main pattern in Maximum Value of an Ordered Triplet II?

The main pattern is prefix and suffix preprocessing around the middle index j. Instead of picking every triplet, you precompute the best left value before j and the best right value after j, then evaluate the formula in constant time per middle position.

Why does checking each middle index j work?

Once j is fixed, the formula becomes independent on each side. You want the largest nums[i] on the left to maximize nums[i] - nums[j], and the largest nums[k] on the right to maximize the final multiplication.

Why is the answer 0 for some arrays even when triplets exist?

The problem says to return 0 if all ordered triplets produce a negative value. That means you still evaluate valid triplets, but you do not return a negative maximum at the end.

Do I need prefix and suffix arrays for this problem?

They are the clearest way to express the solution because they make the ordered constraint explicit and keep each middle-index calculation O(1). In interviews, this is usually the most readable version of the linear-time approach.

What type should I use for the product?

Use 64-bit arithmetic such as long long in C++ or long in Java. Even though each nums value fits in normal integer range, the product of a large difference and a large suffix value can overflow 32-bit integers.

#2874

Medium

auto_awesome数组·driven

LeetCode 题解工作台

有序三元组中的最大值 II

给你一个下标从 0 开始的整数数组 nums 。请你从所有满足 i 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。示…

数组

题目描述

给你一个下标从 0 开始的整数数组 nums 。

请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。

下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。

示例 1：

输入：nums = [12,6,1,2,7]
输出：77
解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
可以证明不存在值大于 77 的有序下标三元组。

示例 2：

输入：nums = [1,10,3,4,19]
输出：133
解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
可以证明不存在值大于 133 的有序下标三元组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。

提示：

3 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

lightbulb

解题思路

方法一：维护前缀最大值和最大差值

我们用两个变量 $\textit{mx}$ 和 $\textit{mxDiff}$ 分别维护前缀最大值和最大差值，用一个变量 $\textit{ans}$ 维护答案。初始时，这些变量都为 $0$ 。

接下来，我们枚举数组的每个元素 $x$ 作为 $\textit{nums}[k]$ ，首先更新答案 $\textit{ans} = \max(\textit{ans}, \textit{mxDiff} \times x)$ ，然后我们更新最大差值 $\textit{mxDiff} = \max(\textit{mxDiff}, \textit{mx} - x)$ ，最后更新前缀最大值 $\textit{mx} = \max(\textit{mx}, x)$ 。

枚举完所有元素后，返回答案 $\textit{ans}$ 。

时间复杂度 $O(n)$ ，其中 $n$ 是数组长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        ans = mx = mx_diff = 0
        for x in nums:
            ans = max(ans, mx_diff * x)
            mx_diff = max(mx_diff, mx - x)
            mx = max(mx, x)
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice that j is the fixed middle and the formula can be split into best left and best right choices.
question_mark
They expect you to reject O(n^3) triplet enumeration and move to prefix and suffix preprocessing.
question_mark
They may watch whether you remember the answer is 0 when the best computed product is still negative.

warning

常见陷阱

外企场景

error
Using the global maximum on the left or right without enforcing i < j < k, which breaks the ordered triplet condition.
error
Forgetting to clamp the final result to 0, which gives the wrong answer on arrays like [1,2,3].
error
Computing the product in a type that is too small, since values can exceed 32-bit integer range during multiplication.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Replace the right-side maximum with a suffix minimum if the formula changes and the multiplier can benefit from smaller values.
arrow_right_alt
Ask for the indices of the optimal triplet instead of only the value, which means storing where each prefix and suffix maximum came from.
arrow_right_alt
Convert the same ordered-triplet idea into a streaming version where you maintain the best left value and best left-minus-middle score as you scan.

help

常见问题

外企场景

继续练习

#2873 有序三元组中的最大值 I #2875 无限数组的最短子数组 #2871 将数组分割成最多数目的子数组