algorithm - 面试题: Buy and sell stocks to maximize profit with constraint of not buying once you sell

Question

有一个经典的面试问题，利润最大化，一次交易买股票，允许n次交易和k次交易。

有人问我类似的问题，但有一个扭曲约束:您可以多次购买股票(任何一天不超过一个单位)，但您不能在卖出股票后购买。

这有一个你只卖一次的引理。

例如:70 40 90 110 80 100

选项 1:B B B 卖出 _ _ = 130

选项 2:B B B X B 卖出 = 120

老问题

https://www.geeksforgeeks.org/stock-buy-sell/

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-twice/

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/

https://www.geeksforgeeks.org/maximum-profit-after-buying-and-selling-the-stocks-any-number-of-times/

Stackoverflow 讨论

maximizing profit for given stock data via DP

Maximizing profit for given stock quotes

Maximum profit by buying and selling a share exactly k times

Best time to Buy and Sell stock modified version

Answer 1

这可以在 O(n lg n) 中解决与 O(n)使用 BST 的空间。

数据结构

class BSTNode{
    BSTNode(val){
        this.val = val
        this.sum = sum
        this.left = this.right = null
        this.count = 1
    }

    insert(val){
        if(val < this.val)
            insert val into the left subtree
        else if(val > this.val)
            insert val into the right subtree

        this.sum += val
        this.count++
    }

    count_sum_nodes_upper_bound(val){
        if(val < this.val)
            return this.left.sum_nodes_lower_bound(val)
        else if(val == this.val)
            return this.left.sum, this.left.count
        else{
            right_sum, right_count = this.right.sum_nodes_lower_bound(val)

            return (this.sum - this.right.sum + right_sum),
                   (this.count - this.right.count + right_count)
        }
    }
}

以上只是适当的 BST 应该是什么样子的粗略概述。在实践中，您可能希望改用平衡树并检查 count_sum_nodes_lower_bound 中是否存在子树。 .上面代码解释:

每个BSTNode除了 BST 的标准属性外，还拥有属性 sum和 count , 其中count是子树中元素的数量，sum是其中所有元素的总和。

Insert 的工作方式与它在普通 BST 中的工作方式相同，除了在每个节点中对应的 sum。和 count需要更新。如果多次插入相同的值，sum和 count将更新以反射(reflect)口是心非。

然而，核心部分是方法 count_sum_nodes_upper_bound ，计算给定上限的元素计数及其总和。对于给定的上限 b值 v 的节点上可能发生三种情况:

• b < v : 所有相关的元素都包含在左子树中
• b == v : 左子树为查询结果
• b > v :左子树和当前节点中的所有值都是子集的一部分。另外右子树的一些节点也是结果的一部分，我们需要通过递归找到。

搜索

有了这个 BST，我们现在可以轻松找到上述问题的解决方案:

maximize_profit(A){
    node = BSTNode(A[0])
    max = 0
    max_idx = -1

    for(i in 1..(A.length - 1)){
        sum, count = node.count_sum_nodes_upper_bound(A[i])
        gain = A[i] * count - sum 

        if(max < gain){
            max = gain
            max_idx = i
        }

        node.insert(A[i])
    }

    return max_idx
}

上述代码根据存储在 BST 中的值找到最佳销售日期的索引。在迭代开始时 i , node将包含 A[0..i - 1] 中的所有值.唯一值得购买的股票是那些值(value)低于 A[i] 的股票.我们可以在O(lg n)中查询这些股票的数量和总和。使用 count_sum_nodes_upper_bound .如果总和为 s，则这些股票的总 yield 和他们的数量 c然后是所有股票的卖出价 (A[i] * c) 减去每只股票的买入价 (s)。

购买股票之后可以在 O(n) 中轻松完成通过过滤A (或根据您的需要扩展 BST 的功能)。