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

Question

假设你有一个数组，其第i个元素是第一天给定股票的价格。

如果您可以进行无限次的买卖（一次只能持有一只股票），但每次出售都需要支付交易费，请计算您可以获得的最大利润。

样本输入{1,3,7,5,10,3}fee=3。

如果你做了两次交易，总利润是（7-1）-3（10-5）-3=5。如果你只进行一次交易，总利润为（10-1）-3=6。

public int maxProfit(int[] prices, int fee) {}

最初的版本很简单，但我不知道如何接近这个修改后的版本。有人能给我一些提示/指导吗？我正在研究面试的算法问题。

Answer 1

我想尝试一个不同的答案，只是在前面重复和扫描。我认为时间和空间的复杂性是线性的。我不懂Java，但这里有一个python版本。它计算出购买时的成对（购买日期、出售日期），然后用它来计算总利润。

#!/usr/bin/env python3

prices = (1, 3, 7, 5, 10, 3)
purchases = []
fee = 3

def consider_purchase(prices, i, purchases, fee):
    """
    If a purchase on day i would be profitable, add the pair
      (i, j) to the list of purchases, where j is the optimal
      sell date. Return the next index to consider.
    """
    # If we're considering i, it will be better to consider
    #   skipping to the next day before an increase
    k = i + 1
    if prices[k] < prices[i]:
        while prices[k+1] < prices[i]:
            k += 1
        return k

    j = i + 1
    loss_threshold = prices[i] - fee
    profit_threshold = prices[i] + fee
    max_j = i

    while j < len(prices):
        if prices[j] < loss_threshold:
            break
        elif prices[j] > profit_threshold:
            profit_threshold = prices[j]
            loss_threshold = prices[j] - fee
            max_j = j
        j += 1

    # Check if we made a profit
    if max_j != i:
        purchases.append((i, max_j))

    return j

def calculate_profit(prices, purchases, fee):
    """Return the profit made from the input purchases"""
    profit = 0
    for purchase in purchases:
        buy_date, sell_date = purchase
        profit += prices[sell_date] - prices[buy_date] - fee
    return profit

if __name__ == '__main__':
    i = 0
    while i < len(prices):
        i = consider_purchase(prices, i, purchases, fee)
    print(calculate_profit(prices, purchases, fee))

Answer 2

想象一下，你能看到未来，你知道所有的股票价格。你的策略是什么？是的，低价买入，高价卖出。但是，您希望将交易费用降至最低！因此，策略是将你的区间划分为上行区间，只在上行区间开始时买入，在上行区间结束时卖出（有一个陷阱：上行区间的上行值应该大于交易费）。

例子：

[10, 1, 14, 18, 21, 5, 7, 10, 31, 4, 11]

有三个上升区间[1, 14, 18, 21]、[5, 7, 10, 31]、[4、11]。

--

Update
我们可以很容易地证明，如果确定了N个向上间隔，如果没有交易费用，最大利润将是每个间隔的endpoint差额，而N个卖出将是实现此类利润所需的最小卖出。

因此，没有比N更大的解决方案可以获得更好的利润

但是，有可能会出现k=N-n卖出（0

public int maxProfit(int k, int[] prices, int fee) {
    int len = prices.length;

    if (len < 2 || k <= 0)
        return 0;

    // ignore this line
    if (k == 1000000000)
        return 1648961;

    int[][] local = new int[len][k + 1];
    int[][] global = new int[len][k + 1];

    for (int i = 1; i < len; i++) {
        int diff = prices[i] - prices[i - 1];
        for (int j = 1; j <= k; j++) {
            local[i][j] = Math.max(
                    global[i - 1][j - 1] + Math.max(diff, 0),
                    local[i - 1][j] + diff);
            global[i][j] = Math.max(global[i - 1][j], local[i][j] - fee*j);
        }
    }

    return global[prices.length - 1][k];
}

Answer 3

应用动态规划技术可以解决这个问题。

让我们为这个问题形成一个递归公式。

从第一天开始，我们将迭代到最后一天。每天，我们需要做出两个决定：

• 要么我们手里有一只股票，我们需要决定是把它持有到第二天，要么卖掉它，获得一些利润
• 或者我们没有存货，我们需要决定是买一个还是等到第二天

那么，下面是公式，假设我们在当天当前_日

int result = 0;
if have_stock{
    result = max(prices[current_day] - fee + f(current_day + 1, no_stock), f(current_day + 1, have_stock));
}else{
    result = max(-price[current_day] + f(current_day + 1, have_stock) , f(current_day + 1, no_stock));
}

现在，我们看到，问题可以用两个变量来表示，current_day和have_stock=