面试问题:买卖股票以最大化利润，约束条件是卖出后不再买入

Question

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

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

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

例如: 70 40 90 110 80 100

选项1:B销售__= 130

选项2:B x B Sell = 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

这可以在使用BST的O(n)空间的O(n lg 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_sum_nodes_lower_bound中是否存在子树。上面的代码解释：

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

Insert的工作方式与它在普通BST中的工作方式相同，只是在每个节点中需要更新相应的sum和count。如果多次插入相同的值，则会更新sum和count以反映重复项。

但是，核心部分是count_sum_nodes_upper_bound方法，它计算给定上界的元素计数及其总和。对于给定的上限b，值为v的节点上可能出现三种情况

• b < v：所有相关的元素都包含在left-subtree
• b == v：中，左子树是query
• 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]中的所有值。唯一有意义的股票是那些价值低于A[i]的股票。我们可以使用count_sum_nodes_upper_bound在O(lg n)中查询这些股票的数量和总和。如果这些股票的和是s并且它们的count c，那么从这些股票中获得的总收益就是所有股票的卖出金额(A[i] * c)减去每只股票的买入价值(s)。

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

Answer 2

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

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]