JZX轻语：简
LeetCode 2873&2874 - 有序三元组中的最大值 II
发表于2025年04月05日
比较套路的题目，我们可以使用两个变量来分别维护已枚举的前缀中的最大值和当前的最大差值。我们从左到右遍历数组，更新这两个变量，并在每次迭代中计算当前的最优解。最终返回结果即可。
class Solution {
public:
long long maximumTripletValue(vector<int>& nums) {
long long prev_max_elem = max(nums[0], nums[1]);
long long prev_max_diff = nums[0] - nums[1];
long long result = 0; // 因为题目要求如果最优解为负数, 则返回0, 因此初始值为0没问题
for (int i = 2; i < nums.size(); ++i) {
// 先使用前面已枚举的前缀中的最大差值, 计算使用当前元素的最优解
result = max(result, prev_max_diff * nums[i]);
// 再使用当前元素更新前缀中的最大差值以及最大值
prev_max_diff = max(prev_max_diff, prev_max_elem - nums[i]);
prev_max_elem = max(prev_max_elem, static_cast<long long>(nums[i]));
}
return result;
}
};