Shouyu

Appearance

买卖股票最佳时机 ​

题目描述 ​

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

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

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

示例 1：

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

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

文章讲解：https://programmercarl.com/0121.买卖股票的最佳时机.html

思路 ​

题目特别强调不能当天买当天卖，因此不能像买卖股票的最佳时机 II那样做。

而且股票只能买卖一次，因此就是找靠左的一个最小值，靠右的一个最大值。

暴力解法 ​

双层for循环，不断找两个元素的最大差值。必须保持右减左。

贪心解法 ​

从左向右依次遍历，找当前最小值作为靠左最小价格。不断计算当前价格与最左最小价格的最大差值。

C++
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
};

动规五部曲 ​

1、dp数组及下标含义 ​

对于每天，都有持有和不持有两个状态，两个状态都有最多现金。

因此定义：

dp[i][0] 表示第i天持有股票所得最多现金 ，这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？

其实一开始假设现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。

dp[i][1] 表示第i天不持有股票所得最多现金

2、递推公式 ​

如果第 i 天持有股票即dp[i][0]， 那么可以由两个状态推出来

  • 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
  • 第 i 天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第 i 天不持有股票即dp[i][1]， 也可以由两个状态推出来

  • 第 i-1 天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
  • 第 i 天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3、dp数组初始化 ​

根据递推公式，需要上层信息，那么初始化第一层。

dp[0][0]表示第0天持有股票，所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票，即没买，所以不欠钱，dp[0][1] = 0;

4、确定遍历顺序 ​

从前向后遍历，按时间推进

5、举例推导 ​

示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：

121.买卖股票的最佳时机

最终返回值时应该返回最后一天不持有股票所能获得的最大金额，因为持有是一定欠钱的。

代码实现 ​

C++
int maxProfit(vector<int>& prices) {
    vector<vector<int>> dp(prices.size(),vector<int>(2));
    dp[0][0] = -prices[0];// 第i天持有股票能获取的最大利润
    dp[0][1] = 0;
    for(int i = 1;i < prices.size();i++){
        dp[i][0] = max(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];
}