Leetcode 2921. 价格递增的最大利润三元组 II

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 = n
        self.nums = [-inf] * n
        self.arr = [-inf] * n
    
    def 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 = -inf
        index = right
        while index >= left:
            # l维护index维护的区间的左端点下标；如果l>=left，说明index维护的区间在[left,right]闭区间中，所以可以算最大值，反之，只能从原数组nums中选择，并将index自减1
            l = index - self.lowerbit(index + 1) + 1
            if l >= left:
                ans = max(ans, self.arr[index])
                index = l - 1
            else:
                ans = max(ans, self.nums[index])
                index -= 1
        return ans


class 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] * n
        for i in range(n):
            leftMax = treeArr1.queryMax(0, prices[i] - 1)
            larr[i] = leftMax
            treeArr1.update(prices[i], profits[i])
        rarr = [-inf] * n
        for j in range(n - 1, -1, -1):
            rightMax = treeArr2.queryMax(prices[j] + 1, maxPrice)
            rarr[j] = rightMax
            treeArr2.update(prices[j], profits[j])
        # 第三步，根据larr和rarr和profits数组提取题解
        result = -1
        for 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 = n
        self.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 + start
        if 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 + start
        if 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))
    
    # 封装change
    def update(self, index:int, val:int) -> None:
        return self.change(index, val, 0, 0, self.n - 1)

    # 封装rangeMax
    def 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和rarr
        larr = [-inf] * n
        for i in range(n):
            leftMax = segTree1.getRangeMax(0, prices[i] - 1)
            larr[i] = leftMax
            segTree1.update(prices[i], profits[i])
        # 
        rarr = [-inf] * n
        for j in range(n - 1, -1, -1):
            if prices[j] + 1 <= maxPrice:
                rightMax = segTree2.getRangeMax(prices[j] + 1, maxPrice)
                rarr[j] = rightMax
            segTree2.update(prices[j], profits[j])
        # 第三步，根据larr和rarr和profits数组提取题解
        result = -1
        for 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.执行结果