leetcode 2874. 有序三元组中的最大值 II 中等

给你一个下标从 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^5
• 1 <= nums[i] <= 10^6

分析：由于数组的规模扩大到了10的5次方，因此不能用暴力的方法。可以采用枚举 j，或者枚举 k的方法解决。

枚举 j 时，可以用一个前缀数组，记录 0 - j-1 中的最大值；一个后缀数组，记录 j+1 - length 中的最大值，每次对于当前的 j，计算一个三元组值，保留最大结果。

枚举 k 时，当 nums[i]-nums[j] 的值最大时，三元组的值最大。可以用 imax 维护 nums[i] 的最大值，dmax 维护 nums[i]−nums[j] 的最大值，在枚举 k 的过程中，更新 dmax 和 imax。注意着三个值的维护顺序。每次先更新答案，也就是三元组的值；枚举的是 k，也就是 nums[k]；第二个更新的是差值；最后更新 nums[i]。

long long maximumTripletValue(int* nums, int numsSize) {long long ans=0,num_i,num_d;num_i=num_d=0;for(int k=0;k<numsSize;++k){ans=fmax(ans,num_d*nums[k]);num_d=fmax(num_d,num_i-nums[k]);num_i=fmax(num_i,nums[k]);}return ans;
}