121. 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)

"给血雨腥风的二级市场留下八个大字——巴菲特就那么回事"

题目链接：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$, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

前置分析

由于条件限制多，我们进行逐一分析

1. 定义交易：一买一卖才算是一次完整交易（仅买入不算一次交易）；

2. 定义利润：融资炒股，手上没有本金（空手套白狼），如果交易后，手上还有钱，那就是利润；

3. 当手上持有股票时，只能选择持有或卖出，不能买入股票；

4. 由于最多交易一次，即某天卖出后，交易次数达一次，次日及以后将不能再交易。

为何能用动归来解决？动归的充要条件：

1. 最值问题？ 求第 $n$ 天的最大利润，$n=prices\mathrm{.}length-1$；
2. 无后效行？ 没有要求指出具体哪天买入、哪天卖出时利润最大；
3. 最值可以穷举？ 穷举任意 $i_1$ 和 $i_2$（）之间的差值；$O(n^2)$ 算法可以获得最大利润；
4. 最优子结构？ 如果知道第 $n-1$ 天的最大利润，是否能推出来第 $n$ 天的最大利润

方法1: 中规中矩的动态规划

1、确定 dp 状态数组以及含义

定义 $dp[i][j][k]$，第 $i$ 日，持股状态为 $j$，交易次数 $k$ 时，最大利润

其中，

• $i$ 为天数，$i\in [0,prices\mathrm{.}length)$；

• $j$ 为持股状态，$j=0\text{、}1$，$0$ 为未持股状态，$1$ 为持股状态；

• $k$ 为交易次数，$k=0\text{、}1$，$0$ 为尚未交易过，$1$ 为交易一次；

2、确定 dp 状态转移方程

第 $i$ 天，未持股，交易 $0$ 次，不管是哪天，不持股也不交易，手上的现金均为 $0$，即 $dp[i][0][0]=0$

第 $i$ 天，未持股，交易 $1$ 次，即$dp[i][0][1]$，手上的现金就有两种可能：

• 第 $i-1$ 天，持股，交易 $0$ 次，第 $i$ 天卖出（交易变为1次），即 $dp[i-1][1][0]+prices[i]$

• 第 $i$ 天，未持股，交易 $0$ 次，即 $dp[i-1][0][1]$

  我们取两者的最大值，即 $dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])$

第 $i$ 天，持股，交易 $0$ 次，即 $dp[i][1][0]$，手上的现金就有两种可能：

• 第 $i-1$ 天，未持股，交易 $0$ 次，但第 $i$ 天买入，即 $dp[i-1][0][0]-prices[i]$

• 第 $i-1$ 天，持股，交易 $0$ 次，但第 $i$ 天什么也不干，即 $dp[i-1][1][0]$

  我们取两者的最大值，即 $dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])$

第 $i$ 天，持股，交易 $1$ 次，即 $dp[i][1][1]$，手上的现金就有两种可能：

• 第 $i-1$ 天，未持股，交易 $1$ 次，但第 $i$ 天买入，即 $dp[i-1][0][1]-prices[i]$

• 第 $i-1$ 天，持股，交易 $1$ 次，但第 $i$ 天什么也不干，即 $dp[i-1][1][1]$

  我们取两者的最大值，即 $dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])$

3、确定 dp 初始状态

• $dp[0][0][0]=0$ ，代表第 $0$ 天不持股且尚未交易时，手上最大的利润；

• $dp[0][0][1]=-infinity$，代表第 $0$ 天不持股且交易 $1$ 次，我们手上的现金（一买一卖才算一次交易，至少需要两天，所以这是不可能的状态，使用一个全局最小值初始化）；

• $dp[0][1][0]=-prices[0]$，代表第 $0$ 天持股但还尚未交易时，手上最大的利润；

• $dp[0][1][1]=-infinity$，代表第 $0$ 天持股且交易 $1$ 次，手上最大的利润（这是不可能的状态）。

4、确定遍历顺序

从第 $1$ 天遍历到第 $prices\mathrm{.}length-1$ 天

5、确定返回值

第 $n-1$ 天的最大利润，一定是手上不持股时的利润（即 $j=0$），所以最大利润有两种情况，即

• 第 $n-1$ 天，不持有股票，交易 $0$ 次，即 $dp[n-1][0][0]$ （这个值必为0，因为既不持股，也不交易，是不可能获得利润的）

• 第 $n-1$ 天，不持有股票，交易 $1$ 次，即 $dp[n-1][0][1]$

故，最终返回值为 $max(dp[n-1][0][0],dp[n-1][0][1])$ 或 $max(0,dp[n-1][0][1])$

6、上代码

/**
 * 空间复杂度 O(n), n 是 prices 数组的长度
 * 时间复杂度 O(n)
 */
function maxProfit(prices: number[]): number {
    const n = prices.length;

    if (n < 2) return 0;

    const dp = new Array(n).fill(0).map(() => [0,0].map(() => [0, 0]));

    dp[0][0][0] = 0;
    dp[0][0][1] = Number.MIN_SAFE_INTEGER;
    dp[0][1][0] = -prices[0];
    dp[0][1][1] = Number.MIN_SAFE_INTEGER;

    for(let i = 1; i < n; i ++) {
        dp[i][0][0] = 0;
        dp[i][0][1] = Math.max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1]);
        dp[i][1][0] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);
        dp[i][1][1] = Math.max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);
    }

    return Math.max(dp[n-1][0][0], dp[n-1][0][1]);	
}

方法2: dp 维度压缩的动态规划

既然只关心最大利润值，可以试想: 存在 $i_1$ 与 $i_2$，且 $0\le i_1<i_2<n$， $prices[i_1]$ 为 $prices$ 中最小值，$prices[i_2]$ 为 $(i_1,n)$ 区间的最大值，那么最大利润即为 $prices[i_2]-prices[i_1]$，其中 $n=prices\mathrm{.}length$。

1、确定 dp 状态数组以及含义

故定义：$dp[i]$ 为天数区间 $[0,i]$ 的最大利润。

2、确定 dp 状态转移方程

当前日的最大利润 $dp[i]$ 一定是前一日的最大利润 $dp[i-1]$ 与当天 $prices[i]$ 与前 $i$ 天的最小股票价格之间中的最大值（还额外需要一个值记录当前的 $minprice$）, 即$dp[i]=max(dp[i-1],prices[i]-minprice)$

3、确定 dp 初始状态

第 $0$ 天的最大利润必为 $0$，即 $dp[0]=0$。

4、确定遍历顺序

从第 $1$ 天遍历到第 $n-1$ 天

5、确定返回值

最终要寻求区间 $[0,n-1]$ 的最大利润，即 $dp[n-1]$。

6、上代码

/**
 * 空间复杂度：平均 O(n)
 * 时间复杂度：平均 O(n)
 */
function maxProfit(prices: number[]): number {
    const dp = new Array(prices.length).fill(0);
    let minprice = prices[0];

    for(let i = 1, len = prices.length; i < len; i ++) {
        minprice = Math.min(prices[i], minprice);
        dp[i] = Math.max(dp[i - 1], prices[i] - minprice);
    }

    return dp[dp.length - 1];
}

方法3: dp 空间压缩的动态规划

从分析（法2）的状态方程得知，

• $dp$ 数组中第 $i$ 位的值仅与第 $i-1$ 位的值有关，故可将整个 $dp$ 数组的状态压缩成一个状态，记作 $currprofit$，每次使用 $currProfit$ 与 $prices[i]-minprice$ 比较，并将较大值重新赋值给 $currProfit$ 即可

• 初始值为 $currprofit=0$ (初始值取0的原因是: $currProfit=dp[0]$)

示例代码

/**
 * 空间复杂度：平均O(1)
 * 时间复杂度：平均O(n)
 */
function maxProfit(prices: number[]): number {
    let currprofit = 0, minprice = prices[0];

    for(let i = 1, len = prices.length; i < len; i ++) {
        minprice = Math.min(prices[i], minprice);
        currprofit = Math.max(currprofit, prices[i] - minprice);
    }

    return currprofit;
}

方法4: 思路拓展双指针法（非动态规划）

慢指针（左指针）：用于找到 $prices$ 中最小值，一旦找到，该指针不再继续

快指针（右指针）：用于遍历 $prices$，计算当前利润 $currprofit$

示例代码

/**
 * 空间复杂度：平均O(1)
 * 时间复杂度：平均O(n)
 */
function maxProfit(prices: number[]): number {
    let left = 0, right = 0, currprofit = 0;
    const len = prices.length;

    while(right < len) {
        if (prices[left] < prices[right]) {
            // prices[right] 就是当前的价格
            // prices[left] 就是当right天以前的最小值
            currprofit = Math.max(currprofit, prices[right] - prices[left]);
        } else {
            left = right;
        }

        right += 1;
    }

    return currprofit;
}