算法练习8——有序三元组中的最大值

LeetCode 100088 有序三元组中的最大值 I
LeetCode 100086 有序三元组中的最大值 II

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

简单题我重拳出击，中等题我唯唯诺诺

蛮力法

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        array = [0] * len(nums)
        for i in range(2, len(nums)):
            for j in range(i):
                for k in range(j, i):
                    array[i] = max(array[i], (nums[j] - nums[k]) * nums[i])
        return max(array)
            
1
2
3
4
5
6
7
8
9

上面开的数组可以省略

贪心？？？
这应该是最优解了，思路如下：

1. 目标是获取全局(nums[i] - nums[j]) * nums[k]最大值
2. 转化问题，固定k，算出一个局部最大值序列[(nums[i] - nums[j]) * nums[0]], (nums[i] - nums[j]) * nums[1], ...，然后求序列中最大值
3. 现在需要求nums[i] - nums[j]的最大值，当k=n时，假定nums[i] - nums[j]的最大值为a，此时a是由nums[:n]中的值计算出的，当k=n+1时，假定nums[i] - nums[j]的最大值为b，此时b是由nums[:n+1]中的值计算出的，可以发现，相邻两个nums[i] - nums[j]的最大值计算用的序列差一个最新的nums[n]，此时有这么一个关系k=n时nums[i] - nums[j]的最大值是自身和max(nums[:n]) - nums[n]两者中的最大值
4. 这样有如下代码

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        # 当前最大值
        curr_max = 0
        # 当前最大的 nums[i] - nums[j]
        curr_v = 0
        # 当前最大的 (nums[i] - nums[j]) * nums[k]
        ans = 0
        n = len(nums)
        
        for i in range(n):
            # 答案的最大值根据最大的 nums[i] - nums[j] 和当前数值的乘积更新
            ans = max(ans, nums[i] * curr_v)
            # nums[i] - nums[j] 的最大值根据此前最大值减去当前数值更新
            curr_v = max(curr_v, curr_max - nums[i])
            # 更新前缀最大值
            curr_max = max(curr_max, nums[i])
        return ans

# 作者：小羊肖恩
# 链接：https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23