2921：价格递增的最大利润三元组 II（★★）

Ian

2023-10-30 约 903 字预计阅读 2 分钟次阅读

力扣第 2921 题

题目

给定长度为 n 的数组 prices 和 profits （下标从 0 开始）。一个商店有 n 个商品，第 i 个商品的价格为 prices[i]，利润为 profits[i]。

需要选择三个商品，满足以下条件：

prices[i] < prices[j] < prices[k]，其中 i < j < k。

如果选择的商品 i, j 和 k 满足以下条件，那么利润将等于 profits[i] + profits[j] + profits[k]。

返回能够获得的 最大利润，如果不可能满足给定条件，返回 -1。

示例 1：

输入：prices = [10,2,3,4], profits = [100,2,7,10]
输出：19
解释：不能选择下标 i=0 的商品，因为没有下标 j 和 k 的商品满足条件。
只能选择下标为 1、2、3 的三个商品，这是有效的选择，因为 prices[1] < prices[2] < prices[3]。
答案是它们的利润之和，即 2 + 7 + 10 = 19。

示例 2：

输入：prices = [1,2,3,4,5], profits = [1,5,3,4,6]
输出：15
解释：可以选择任意三个商品，因为对于每组满足下标为 i < j < k 的三个商品，条件都成立。
因此，能得到的最大利润就是利润和最大的三个商品，即下标为 1，3 和 4 的商品。
答案就是它们的利润之和，即 5 + 4 + 6 = 15。

示例 3：

输入：prices = [4,3,2,1], profits = [33,20,19,87]
输出：-1
解释：找不到任何可以满足条件的三个商品，所以返回 -1.

提示：

3 <= prices.length == profits.length <= 50000
1 <= prices[i] <= 5000
1 <= profits[i] <= 10⁶

分析

#1 树状数组

令 f2、f3 分别代表递增二元组、三元组的最大利润
显然递推 f2[i]，要找 j 满足 prices[j]<prices[i] 且 profits[j] 最大，这可以用树状数组维护
递推 f3[i] 同理，要找 j 满足 prices[j]<prices[i] 且 f2[j] 最大
令 f1 为 profits，其实就是两次相同的递推

 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


class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        def update(i, x):
            while i<m:
                t[i] = max(t[i],x)
                i += i&-i

        def get(i):
            res = -inf
            while i:
                res = max(res,t[i])
                i &= i-1
            return res

        n = len(prices)
        m = max(prices)+1
        f = profits[:]
        for _ in range(2):
            t = [-inf]*m
            g = [-inf]*n
            for i,a in enumerate(prices):
                g[i] = profits[i]+get(a-1)
                update(a,f[i])
            f = g
        return max(-1,max(f))

1684 ms

#2 有序集合

注意到假如 prices[i]<=prices[j] 且 f[i]>=f[j]，那么 j 可以去掉
因此用有序集合维护 <prices[i],f[i]>，有用的状态必然是递增的
那么要找 j 满足 prices[j]<prices[i] 且 f[j] 最大，二分查找有序集合中最后一个<prices[i] 的 j 即可
然后插入 i 时
- f[j]<f[i] 时，才需要插入
- 插入时，要去除后面的无效状态

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def maxProfit(self, prices: List[int], profits: List[int]) -> int:
        from sortedcontainers import SortedList
        n = len(prices)
        f = profits[:]
        for _ in range(2):
            g = [-inf]*n
            sl = SortedList([(0,-inf)])
            for i,a in enumerate(prices):
                j = sl.bisect_left((a,))
                g[i] = profits[i]+sl[j-1][1]
                if sl[j-1][1]<f[i]:
                    while j<len(sl) and f[i]>=sl[j][1]:
                        sl.pop(j)
                    sl.add((a,f[i]))
            f = g
        return max(-1,max(f))

851 ms

目录

2921：价格递增的最大利润三元组 II（★★）

题目

分析

#1 树状数组

#2 有序集合

解答