💰121.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

尽可能地在最低点买入，然后在之后的最高点卖出，只买卖一次

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例

示例 1：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105 0 <= prices[i] <= 104

思路

低就买入，高就卖出

贪心思路

由于不知道什么时候是最低点，什么时候是最高点，所以我们默认当前值就是最低点，先进行买入，然后遇到比买入点低的我们就买入，继续向后遍历，总能找到最低的一个买入点

在买入之后，遇到比买入点低的我们就买入，遇到比买入点高的我们就卖出，卖出之后遇到更高利润就更新利润结果，当运行结束之后，就会知道当前股票的最高利润是多少

DP思路

设置两个变量，一个记录买入的价格，一个记录卖出的价格，买入的价格之和前一天进行比较，如果当天买入价格更低，就在当天买入，如果前一天买入的价格更低，就记录这个更低的买入价格

卖出价格也与前一天进行比较，如果价格更高就卖出，价格没有前一天高就记录这个更高的卖出价格

整体的思路还是与贪心的思路一致，两个变量最后保存的都是自己的最值，由于卖出在买入的后面，所以不会出现先卖出再买入的情况，例如[9,2,4,1]，在9卖出，在1买入的情况

dp[i][0]代表第i天买入花费的金额

dp[i][1]代表第i天卖出得到的金额

贪心执行流程

设置两个变量，一个存放买入价格，一个存放结果利润，买入价格的初值就是容器第一个元素的值，结果利润的初值是0

之后遍历容器，遇到低就买入，遇到高就卖出，这样设置之后，“最高点”之前的买入点肯定是最低的，这里的最高点不是全局最高，例如[6，7，1，5]，“最高点”肯定是5而不是7

而遍历的过程中肯定会遇到这种“最高点”，而由于程序的逻辑是低就买入，所以一定会得到“最高点”之前的最低点

有更大利润就更新结果，最后得出最大利润

DP执行流程

1. 初始化dp数组，本题中的dp数组是二维的，每一行对应一天，每一天都有两个金额，一个买入一个卖出，初始dp[0][0]= - prices[0]，dp[0][1]=0

2. 更新dp数组的两个值，当天价格比买入价格低就买入，当天价格比卖出价格高就卖出 $$ \begin{align} dp[i][0]=&min(dp[i-1][0],prices[i])\ dp[i][1]=&max(dp[i-1][1],prices[i]-dp[i-1][0]) \end{align} $$ 其中公式1代表昨天买入和今天买入谁花的钱多

   公式2代表昨天卖出和今天卖出谁剩下的钱多，今天卖出时剩下的钱等于今天的价格减去之前最低的价格，就是剩下的金额，其中dp[i-1][0]代表之前最低的买入价格

3. 最后返回dp数组最后剩下的元素，dp[i-1][1]代表最终的结果

代码

根据以上分析，得出以下代码：

贪心

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy=prices[0];
        int res=0;
        for(auto num:prices){
            //低就买入
            if(num<buy){
                buy=num;
            }
            //高就卖出
            if(num>buy){
                //利润更高就更新res
                res=(num-buy)>res?(num-buy):res;
            }
        }
        return res;
    }
};

DP

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==1)
            return 0;
            vector<vector<int>> dp(prices.size(),vector<int>(2,0));
            //初始化数组
            dp[0][0]=prices[0];
            for(int i=1;i<prices.size();++i){
                //低就买入
                dp[i][0]=min(dp[i-1][0],prices[i]);
                //高就卖出
                dp[i][1]=max(dp[i-1][1],prices[i]-dp[i-1][0]);
            }
            return dp[prices.size()-1][1];
    }
};

总结

将当前位置当成最低点买入，遇到更低的价格就买入，遇到更高的价格就卖出，出现更高利润就更新，相当于模拟出所有的买入和卖出的情况，从而可以挑选出最高的利润

DP看起来比贪心更加麻烦，但是各有优点，当前点的买入和卖出价格只与前面有关，所以也符合动态规划的思想，dp数组其实可以进一步缩小，因为之前的结果都累计到了dp[i-1]上，所以只需要一个2*2的dp数组即可