121. 买卖股票的最佳时机

题目:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

解法一:数学分析

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int max = 0;
        int min = INT_MAX;
        for(int i=0;i<prices.size()-1;i++){
            min = (min<prices[i])?min:prices[i];
            int profit = prices[i+1] - min;
            max = (max>profit)?max:profit;
        }
        return max;
    }
};
  1. 我们设dp[i]表示在,如果卖出点是「i」,则获得利润为dp[i]

  2. 不难发现,dp[i]有如下表达式

    $$dp[i] = prices[i] - min(p[0],p[1]...p[i-1])$$

  3. 则我们只需要在遍历的时候记录,在「i」天之前的最低价格,并用当天的卖出价减去即可

解法二:动态规划

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

解法三:解法二动态规划优化

  1. 我们发现解法二每次只用到相邻两行,且每次只有从0到1的变化而没有从1到0的变化,则可以将其简化为一维数组
class Solution {
public:
    int max(int a, int b){return a>b?a:b;}
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len < 2) return 0;
        int dp[2];
        dp[0] = 0;
        dp[1] = -1 * prices[0];
        for(int i=1;i<len;i++){
						dp[0] = max(dp[0],dp[1]+prices[i]);
						dp[1] = max(dp[1], -1 * prices[i]);
        }
        return max(dp[0],dp[1]);
    }
};
  1. 状态dp[i][j]表示,在索引为i的这一天,用户手上持股状态为j的最大利润
  2. 显然,j的取值只有0或者1。即是否持有当天的股票
  3. 转移方程如下
  4. 总结如下:

解法四:差分数组

class Solution {
public:
    int max(int a, int b){return a>b?a:b;}
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len < 2) return 0;
        int diff[len-1];
        for(int i=0;i<len-1;i++){
            diff[i] = prices[i+1] - prices[i];
        }
        int dp[len-1];
        dp[0] = diff[0];
        int result = 0; // 初值设为0是为了考虑不交易的情况
        for(int i=1;i<len-1;i++){
            dp[i] = max(dp[i-1]+diff[i],diff[i]);
            result = max(result,dp[i]);
        }
        return max(result,dp[0]);
    }
};