股票交易的最大收益

题目链接

Solution

已经知道每一天股票的价格，可以无限次交易，每天只能进行一次，询问最大收益。
这类问题可以动态规划解决。
设表示到第i天的时候，最大收益是多少。
首先可以直接从上一天继承过来，即。
其次，如果在第i天卖出，那么需要选择一天买入，设第j天买入，则
如果第i天买入的话，到i后面的时候，会枚举到在第i天买入的情况。
这样做是的。

观察转移方程发现，对于一个j是固定的，所以用一个变量记录下这个式子的最大值即可。
复杂度

Code

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size(); 
        int f[n + 10], mx = -prices[0];
        f[0] = 0;
        for (int i = 1; i < n; ++i) {
            f[i] = max(f[i - 1], mx + prices[i]);
            mx = max(mx, f[i - 1] - prices[i]);
        }
        return f[n  - 1];
    }
};