牛客对应题目链接：买卖股票的最好时机(一)_牛客题霸_牛客网 (nowcoder.com)
力扣对应题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）
一、分析题目
1、贪心
固定一个点为卖出点，遍历顺序从左往右（如果固定的是买入点，那么遍历顺序就得从右往左）。因为只能买卖⼀次，因此对于第 i 天来说，如果在这天选择卖出股票，应该在 [0, i] 天之内的股票最低点买⼊股票，此时就可以获得最⼤利润。那么，我们仅需维护⼀个前驱最⼩值的变量，并且不断更新结果即可。
2、动态规划
（1）明确 dp 数组以及下标的含义
- dp[i][0]：第 i 天持有股票所得最多现金。
- dp[i][1]：第 i 天不持有股票所得最多现金。
注意：这里是持有，不代表就是当天买入，也有可能是昨天就买入了，今天保持持有的状态
（2）确定递推公式
- 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金，即：dp[i-1][0]。
- 第 i 天买入股票，所得现金就是买入今天的股票后所得现金，即：-prices[i]。
那么d p[i][0] 应该选所得现金的最大值，所以 dp[i][0] = max(dp[i-1][0], -prices[i]);
- 第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金，即dp[i-1][1]。
- 第 i 天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：dp[i-1][0]+prices[i]。
同样，dp[i][1] 取最大的，dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);
（3）初始化
- dp[0][0] 表示第 0 天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以 dp[0][0] -= prices[0];
- dp[0][1] 表示第 0 天不持有股票，不持有股票那么现金就是 0，所以 dp[0][1] = 0;
（4）遍历顺序
从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是从前向后遍历。
二、代码
1、贪心
//值得学习的代码 //牛客AC代码 #include <iostream> using namespace std; const int N = 1e5 + 10; int n; int arr[N]; int main() { cin >> n; for(int i = 0; i < n; i++) cin >> arr[i]; int res = 0, prevMin = arr[0]; for(int i = 1; i < n; i++) { prevMin = min(prevMin, arr[i]); res = max(res, arr[i] - prevMin); } cout << res << endl; return 0; } //力扣AC代码 class Solution { public: int maxProfit(vector<int>& prices) { int res=0; int prev_min=prices[0]; for(int i=1; i<prices.size(); i++) { res=max(res, prices[i]-prev_min); prev_min=min(prev_min, prices[i]); } return res; } };
2、动态规划（优化）
//牛客AC代码 #include <iostream> using namespace std; const int N=1e5+10; int prices[N], dp[N][2]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) cin >> prices[i]; dp[0][0]=-prices[0]; for(int i=1; i<n; i++) { dp[i][0]=max(dp[i-1][0], -prices[i]); dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]); } cout << dp[n-1][1] << endl; return 0; } //力扣AC代码 class Solution { //dp[i][0] -- 第i天持有股票所得最多现金 //dp[i][1] -- 第i天不持有股票所得最多现金 public: int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(n, vector<int>(2)); dp[0][0]=-prices[0]; dp[0][1]=0; for(int i=1; i<n; i++) { dp[i][0]=max(dp[i-1][0], 0-prices[i]); dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i]); } return dp[n-1][1]; } }; //优化 class Solution { //dp[i][0] -- 第i天持有股票所得最多现金 //dp[i][1] -- 第i天不持有股票所得最多现金 public: int maxProfit(vector<int>& prices) { int n=prices.size(); vector<vector<int>> dp(2, vector<int>(2)); dp[0][0]=-prices[0]; dp[0][1]=0; for(int i=1; i<n; i++) { dp[i%2][0]=max(dp[(i-1)%2][0], -prices[i]); dp[i%2][1]=max(dp[(i-1)%2][1], dp[(i-1)%2][0]+prices[i]); } return dp[(n-1)%2][1]; } };
三、反思与改进
这道题目最直观的想法，就是用暴力找最优间距了，但很明显用暴力会超时。
我们可以在暴力的基础上优化，就可以想到贪心，因为股票就买卖一次，那么很自然就是取最左最小值，取最右最大值，不断地保留最小的值和当前值进行相减，那么得到的差值就是最大利润。
在做这道题目的时候，想到了贪心这个解法，可是却没有想到如何将 O(N^2) 降到 O(N)。因为这个系列之前都是用动态规划做的，所以先入为主一上来就直接用 dp 做了，初始化考虑的没毛病，但是在买入和卖出的递推关系这里没有理清楚，主要是一直想着当天买入还是卖出，没有想到保持上一天状态用什么表示，把持有和买入没分区分清楚，所以还是 dp 的定义没弄清楚。
