LeetCode算法心得——有序三元组中的最大值 II (简单的动规思想)

大家好，我是晴天学长，枚举＋简单的动态规划思想，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

---

---

1) .有序三元组中的最大值 II

---

有序三元组中的最大值 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 <= 105
1 <= nums[i] <= 106

---

2) .算法思路

有序三元组中的最大值 II
(nums[i] - nums[j]) * nums[k]
枚举k
1.nums[i] - nums[j]) 只用关心这个是不是最大的就可以了

存一个最大差值，存一个最大值（不一定相关）
2.预处理右边最大值，遍历j

---

3) .算法步骤

• 方法1：动态规划，枚举k

1.初始化变量 ans 为 0，preDiff 为 0，preMax 为 0。
2.遍历数组 nums，对于数组中的每个元素 x，执行以下步骤：
3.计算当前三元组的值 preDiff * x，并将其与 ans 进行比较，更新 ans 为较大值。
4.计算当前位置的最大差值 preDiff，更新为当前 preDiff 和 preMax - x 的较大值。
5.计算当前位置的最大元素 preMax，更新为当前 preMax 和 x 的较大值。
6.返回最大值 ans。

• 方法2：预处理右边的最大值，枚举j

1.创建一个长度为 nums.length 的辅助数组 a，用于存储右边元素的最大值。
2.初始化变量 rightDiff 为 0，ans 为 0。
3.从数组 nums 的倒数第二个位置开始向前遍历，执行以下步骤：
4.计算当前位置右边的最大值 rightDiff，更新为当前 rightDiff 和 nums[i] 的较大值。
5.将 rightDiff 存储到辅助数组 a 的相应位置。
6.初始化变量 preMax 为 nums[0]。
7.从数组 nums 的第一个位置开始向右遍历，执行以下步骤：
8.计算当前三元组的值 (preMax - nums[i]) * a[i+1]，并将其与 ans 进行比较，更新 ans 为较大值。
9.计算当前位置的最大元素 preMax，更新为当前 preMax 和 nums[i] 的较大值。
10.返回最大值 ans。

---

4）.代码示例

 class Solution {
        // 方法1，动态规划，枚举k
        public long maximumTripletValue(int[] nums) {
            long ans = 0;
            long preDiff = 0, preMax = 0;
            for (int x : nums
            ) {
                ans = Math.max(ans, preDiff * x);
                preDiff = Math.max(preDiff, preMax - x);
                preMax = Math.max(preMax, x);
            }
            return ans;
        }

        //方法2 预处理右边的最大值,枚举j
        public long maximumTripletValue2(int[] nums) {
            int[] a = new int[nums.length];
            int rightDiff = 0;
            long ans = 0;
            //预处理
            for (int i = nums.length - 1; i > 1; i--) {
                rightDiff = Math.max(rightDiff, nums[i]);
                a[i] = rightDiff;
            }
            //开始遍历
            long preMax = nums[0];
            for (int i = 0; i < nums.length - 1; i++) {
                ans = Math.max(ans, (preMax-nums[i])*a[i+1]);
                preMax = Math.max(preMax,nums[i]);
            }
            return ans;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

5）.总结

• 动态规划，枚举k，j,只用关心上一步的状态和自己的状态。（思想很重要）

---

试题链接：