1.题目基本信息

1.1.题目描述

给定长度为 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.2.题目地址

https://leetcode.cn/problems/maximum-profitable-triplets-with-increasing-prices-ii/description/

2.解题方法

2.1.解题思路

树状数组 / 线段树

2.2.解题步骤

树状数组版本步骤

• 第一步，构建两个树状数组，treeArr1维护左边更小价格对应利润的最大值，treeArr1维护右边更大价格对应利润的最大值

• 第二步，使用树状数组，一边添加元素，一边计算单边最大值，构建larr和rarr数组，分别维护i处左边更小价格对应最大利润，i处右边更大价格对应的最大利润

• 第三步，根据larr和rarr和profits数组提取题解

线段树版本步骤

• 第一步，构建两个线段树，segTree1维护左边更小价格对应利润的最大值，segTree2维护右边更大价格对应利润的最大值

• 第二步，使用线段树，一边添加元素，一边计算单边最大值，构建larr和rarr数组，分别维护i处左边更小价格对应最大利润，i处右边更大价格对应的最大利润

• 第三步，根据larr和rarr和profits数组提取题解

3.解题代码

树状数组版本代码

# ==> 求区间最大值的树状数组（需要维护原数组）
class MaxTreeArr():def __init__(self, n:int):self.n = nself.nums = [-inf] * nself.arr = [-inf] * ndef lowerbit(self, x:int) -> int:return x & (-x)# > 更新原数组的index下标处的元素值为max(nums[index],val)，并更新树状数组中index的祖先结点def update(self, index:int, val:int) -> None:# 注意：这个地方对原数组的更新，一定要取最大值，否则可能导致覆盖最大值导致错误（跳过坑）self.nums[index] = max(self.nums[index], val)while index < self.n:self.arr[index] = max(self.arr[index], val)index += self.lowerbit(index + 1)# > 查找arr闭区间[left,right]之间的最大值def queryMax(self, left:int, right:int) -> int:ans = -infindex = rightwhile index >= left:# l维护index维护的区间的左端点下标；如果l>=left，说明index维护的区间在[left,right]闭区间中，所以可以算最大值，反之，只能从原数组nums中选择，并将index自减1l = index - self.lowerbit(index + 1) + 1if l >= left:ans = max(ans, self.arr[index])index = l - 1else:ans = max(ans, self.nums[index])index -= 1return ansclass Solution:def maxProfit(self, prices: List[int], profits: List[int]) -> int:# 思路一：树状数组n = len(prices)maxPrice = max(prices)# 第一步，构建两个树状数组，treeArr1维护左边更小价格对应利润的最大值，treeArr1维护右边更大价格对应利润的最大值treeArr1 = MaxTreeArr(maxPrice + 1)treeArr2 = MaxTreeArr(maxPrice + 1)# 第二步，使用树状数组，一边添加元素，一边计算单边最大值，构建larr和rarr数组，分别维护i处左边更小价格对应最大利润，i处右边更大价格对应的最大利润larr = [-inf] * nfor i in range(n):leftMax = treeArr1.queryMax(0, prices[i] - 1)larr[i] = leftMaxtreeArr1.update(prices[i], profits[i])rarr = [-inf] * nfor j in range(n - 1, -1, -1):rightMax = treeArr2.queryMax(prices[j] + 1, maxPrice)rarr[j] = rightMaxtreeArr2.update(prices[j], profits[j])# 第三步，根据larr和rarr和profits数组提取题解result = -1for i in range(1, n - 1):if larr[i] + rarr[i] + profits[i] > result:result = max(result, larr[i] + rarr[i] + profits[i])return result

线段树版本代码

# ==> 线段树（维护区间最大值）
class MaxSegmentTree():def __init__(self, n:int):self.n = nself.arr = [-inf] * (4 * n)# 基础函数：修改原数组中的index下标处的元素为val，并更新线段树def change(self, index:int, val:int, node:int, start:int, end:int) -> None:# 第一步，递归退出条件。到达index对应的叶结点if index == start and index == end:# > 防止后面的小元素替换大元素，所以加max（根据具体的修改场景可能会有修改）self.arr[node] = max(self.arr[node], val)return# 第二步，根据mid判断index是在当前node的左子树还是右子树上，并进行递归修改mid = (end - start) // 2 + startif index <= mid:# > index在node左子树的情况self.change(index, val, 2 * node + 1, start, mid)else:# > index在node的右子树的情况self.change(index, val, 2 * node + 2, mid + 1, end)# 第三步，更新当前结点，根据当前结点更新后的左右结点，更新当前结点的最大值self.arr[node] = max(self.arr[2 * node + 1], self.arr[2 * node + 2])# 基础函数：求区间范围内的最大值def rangeMax(self, left:int, right:int, node:int, start:int, end:int) -> int:# 第一步，递归退出条件。当node区间和[left,right]闭区间完全匹配时，递归退出if left == start and right == end:return self.arr[node]# 第二步，递归子问题mid = (end - start) // 2 + startif right <= mid:# > [left,right]区间完全在node结点的左子树区间上return self.rangeMax(left, right, 2 * node + 1, start, mid)elif left > mid:# > [left,right]区间完全在node结点的右子树区间上return self.rangeMax(left, right, 2 * node + 2, mid + 1, end)# > [left,right]区间部分在node的左子树上，部分在右子树上的情况return max(self.rangeMax(left, mid, 2 * node + 1, start, mid), self.rangeMax(mid + 1, right, 2 * node + 2, mid + 1, end))# 封装changedef update(self, index:int, val:int) -> None:return self.change(index, val, 0, 0, self.n - 1)# 封装rangeMaxdef getRangeMax(self, left:int, right:int) -> int:# 注意：left>right时，会导致内存溢出return self.rangeMax(left, right, 0, 0, self.n - 1)class Solution:def maxProfit(self, prices: List[int], profits: List[int]) -> int:# 思路二：线段树n = len(prices)maxPrice = max(prices)segTree1 = MaxSegmentTree(maxPrice + 1)segTree2 = MaxSegmentTree(maxPrice + 1)# 构建larr和rarrlarr = [-inf] * nfor i in range(n):leftMax = segTree1.getRangeMax(0, prices[i] - 1)larr[i] = leftMaxsegTree1.update(prices[i], profits[i])# rarr = [-inf] * nfor j in range(n - 1, -1, -1):if prices[j] + 1 <= maxPrice:rightMax = segTree2.getRangeMax(prices[j] + 1, maxPrice)rarr[j] = rightMaxsegTree2.update(prices[j], profits[j])# 第三步，根据larr和rarr和profits数组提取题解result = -1for i in range(1, n - 1):if larr[i] + rarr[i] + profits[i] > result:result = max(result, larr[i] + rarr[i] + profits[i])print(larr, rarr, profits)return result

4.执行结果