原题链接:
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

解法1:

枚举+维护前缀数组的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
    由于卖出操作必须在买入操作之后
    即该题可理解存在寻找 顺序限制的最大最小值差值问题
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int res = 0;
        // 用于存储最小值
        int m = 1e9; 
        for(int i = 0 ; i < n ; i++){
            m = min(m,prices[i]);
            res = max(prices[i] - m,res);
        }
        return res;
    }
};

动态规划
其实上述解法 其实就是动态规划理解的简化
令f[i] 表示 第i天能买到股票的最低价 则最大利润res = max(prices[i] - f[i],res);
对于f[i]而言 其状态转移方程即为
f[i] = min(prices[i],f[i - 1])
更简化一步 就可以直接用滚动数组的方式进行简化 就变成上面的那种解法