algorithm - 递归股票最大化

Question

问题是根据给定日期的股票价格最大化股票的利润。 我只能买入 1 只股票，卖出任意数量或什么都不做。

Test cases:
Input: 1 2 100
Output: 197
Explanation: Bought on day 1 and day 2 sold on day 3 total profit = (100 - 1) + (100 - 2) = 197

Input: 1 3 1 2
Output: 3
Explanation: buy one share on day 1, sell one on day 2, buy one share on day 3, and sell one share on day 4.

我在下面有一个递归解决方案，我知道还有其他解决方案，但我正在尝试以递归解决方案为基础:

int maxProfit(vector<int> stock)
{
    int profit = helper(stock, stock[0], 1, 1);
    return profit < 0 ? 0 : profit;
}

int helper(vector<int>& stock, int cost, int index, int stockcount)
{
    if (index == stock.size() - 1)
    {
        return (stock[index] * stockcount) - cost;
    }
    int buy = helper(stock, cost + stock[index], index + 1, stockcount + 1);
    int sell = helper(stock, cost - stock[index], index + 1, stockcount - 1);
    return max(buy, sell);
}

该算法是否是正确的递归方法？有没有办法让我记住上面的内容？可能移除累加器 cost?

Answer 1

术语:股票是公司的特定所有权类别，例如英特尔的 INTC 或微软普通股的 MSFT。您买卖的各个分区称为份额。

正如 גלעד ברקן 已经指出的那样，您知道 future 。没有猜测，没有美元平均，没有部分解决方案。你有全部信息。

引理:如果卖出 1 股股票是有意义的，那么卖出你所有的股票也是有意义的。这将大大简化您的算法:您不必探索 1-N 的备选方案。

引理:如果今天的价格低于 future 的最高价，最好的策略是买入允许的最高价。

算法

// Base case:
If the array is empty, return

// Process
Find the maximum price in the array (call that day_s)
Buy max shares (one) on each day 1 : day_s
Sell all shares on day_s
(balance accounting is left as an exercise for the student)

// Recur
helper(stock[day_s: ], balance, 0)