面试问题：买卖股票以实现利润最大化，但有一次卖出就不买的限制

Question

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

有人问我一个类似的问题，但有一个扭曲的限制：你可以购买一只股票任意次数（任何一天不超过一个单位），但你不能在卖出股票后购买。

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

例：70409011080100

选项1:B卖出=130

选项2: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讨论

通过DP实现给定股票数据的利润最大化

给定股票报价的利润最大化

通过买卖股票获得的最大利润正好是k倍

购买和出售股票的最佳时间修改版

Answer 1

我们还可以在O（n log n）时间和O（n）空间中使用数组、堆栈和二进制搜索来解决这个问题。向后迭代并在每次迭代中，如果值高于数组中的最后一个元素，则将（value， index，0,0）（（value， index， count，成本））添加到数组记录中；否则，找到第一个更高的元素（使用二进制搜索），添加到其计数和成本中，并将索引添加到贡献者堆栈中。

0  1  2  3   4  5
70 40 90 110 80 100

i:5
  [(100, 5, 0)]
  contributors: []
i:4
  80 < 100
  [(100, 5, 1, 80)]
  contributors: [4]
i:3
  110 > 100
  [(100, 5, 1, 80), (110, 3, 0, 0)]
  contributors: [4]
i:2
  90 < 100
  [(100, 5, 2, 170), (110, 3, 0, 0)]
  contributors: [2, 4]
i:1
  40 < 100
  [(100, 5, 3, 210), (110, 3, 0, 0)]
  contributors: [1, 2, 4]
i:0
  70 < 100
  [(100, 5, 4, 280), (110, 3, 0, 0)]
  contributors: [0, 1, 2, 4]

现在迭代我们新的、单调增加的记录。在记录上的每次迭代中，添加前一个元组中的计数和成本，然后在贡献者堆栈中每个元素的索引大于记录中的当前索引时“弹出”计数和成本：

0  1  2  3   4  5
70 40 90 110 80 100

[(100, 5, 4, 280), (110, 3, 0, 0)]

i:0
  best = 4 * 100 - 280 = 120

i:1
  add count and cost:
  (110, 3, 0 + 4, 0 + 280)

  pop count and cost for each
  contributor with a greater index:
  contributors: [0, 1, 2, 4]
  index 4 > 3
  (110, 3, 4 - 1, 280 - 80)
    profit = 3 * 110 - 200 = 130
    best = 130
    contributors: [0, 1, 2]

Answer 2

这可以在O（n lg n）中使用BST在O（n）空间中解决。

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\u sum\u nodes\u lower\u bound中。上述代码解释如下：

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

插入的工作方式与在正常BST中的工作方式相同，只是在每个节点中需要更新相应的sum和count。如果相同的值被多次插入，sum和count将被更新以反映双重性。

然而，中心部分是方法count_sum_nodes_upper_bound，它计算给定上限的元素计数及其总和。对于给定的上限b，在具有值v的节点上可能会出现三种情况：

• <代码>b

通过此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，节点将包含A[0..i-1]中的所有值。只有价值低于a[i]的股票才值得购买。我们可以使用count\u sum\u nodes\u upper\u bound在O（lg n）中查询这些股票的数量和总和。如果这些股票的总和是s，而它们的计数是c，那么这些股票的总收益就是所有股票的销售金额（A[i]*c）减去每只股票的购买价值（s）。

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