【错题集-编程题】买卖股票的最好时机（一）（贪心 + 动态规划）

牛客对应题目链接：买卖股票的最好时机(一)_牛客题霸_牛客网 (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 的定义没弄清楚。