LeetCode 121 买卖股票的最佳时机

121.买卖股票的最佳时机

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

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

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

示例

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

动态规划

本题的重点在于递推关系的确定，此处只考虑买入时间，不考虑卖出时间（本质上卖出时间就是最大利润的那一天）：第 i 天买入，能够获得最大利润使用 dp[i] 表示，那么第 i+1 天买入能够获得的最大利润使用 dp[i+1] 表示，那么 dp[i]=max(dp[i+1]+(prices[i]-prices[i-1]),0) ，那么使用动态规划进行求解的过程为：

1. 动态规划数组的定义：定义数组 dp[n+1] 表示第 n 天买入能够获得的最大利润

2. 动态规划数组的推导： dp[i]=max(dp[i+1]+(prices[i]-prices[i-1]),0)

3. 动态规划数组的初始化：对于最后一天买入的股票，必然不能盈利那么 dp[n+1]=0

4. 动态规划数组的遍历顺序：在计算 dp[n] 时需要使用 dp[n+1] 的信息，因此此处需要使用从后向前遍历的方式。

5. 对于 vector<int> prices={7,1,5,3,6,4}; 动态规划数组的输出为： dp=[0,0,3,1,5,0] 验证正确

代码实现：

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

此处仅仅使用到了前一天的状态，那么可以基于滚动数组实现，从而减少空间复杂度：

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

暴力法

本质上就是在一个数组中，寻找两个点之间的最大间距，使用一个双for循环即可完成穷举。

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

这样的实现方式将会超出时间限制。

贪心实现

最简单的思想就是，在左边找到一个最小值，在右边找到一个最大值，做减法即可得到需要求解的值。

在左边寻找最小值的过程，本质上就是在从左向右遍历的过程中记录最小值，让当前值始终与记录的最小值做减法。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==1) return 0;
        int res=0;
        int minp=INT_MAX;
        for(int i=0;i<n;i++){
            minp=min(minp,prices[i]);
            res=max(res,prices[i]-minp);
        }
        return res;
    }
};