题解 | #买卖股票的最好时机(三)#

多个整体状态的DP数组应该保存什么？

• 此题跟打家劫舍（二）的环形房屋都有多状态，环形房屋有两种情况的状态，一个是只选第一个房子不选最后一个房子，一个是只选最后一个房子不选最后一个房子，最后比较这两种状态的DP数组的最大值。
• 由于本题最多只能进行两次股票买卖，因此需要分多个整体状态来分析最大收益值，因此需要一个二维dp数组dp[i][j]，表示第i天股票状态为j的收益，这跟前一天的股票状态有关。一共有五种状态：
• 0表示到第i天为止都从未买过股票的收益，
• 1表示到第i天为止买过一次股票但是没有卖出的收益，
• 2表示到第i天为止买过一次股票也卖过一次的收益，
• 3表示到第i天为止买过两次股票但只卖出一次的收益，
• 4表示到第i天为止买过两次股票并且卖出两次的收益。
• 由于股票整体状态中可能是进行一次股票买卖的收益最高，也有可能是进行两次股票买卖的收益最高，因此要在这两种情况中选最大收益。

最小子问题

• 第1天没有买入股票，收益为dp[0][0] = 0
• 第1天买入股票，收益为dp[0][1] = -prices[0]

如何思考状态转移方程？

股票当天状态的收益跟前一天的状态收益有关：

• 如果当天状态为0，说明至今都没有持有股票，收益为dp[i][0] = dp[i-1][0]
• 如果当天状态为1，说明至今买入过一次股票，则有可能是在今天之前买的，也有可能是在今天买的，取这两种情况的最大值，收益为dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]
• 如果当天状态为2，说明至今买过和卖出一次股票，则有可能在今天之前就买卖过一次股票了，也有可能在今天才第一次卖出股票，取这两种情况的最大值，收益为dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]
• 如果当天状态为3，说明至今买过两次股票和卖过一次股票，则有可能是在今天之前就买过两次股票和卖出一次股票了，也有可能在今天才买入第二次股票，取这两种情况的最大值，收益为dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]
• 如果当天状态为4，说明至今买过两次股票和卖出两次股票，则有可能是在今天之前就买卖过两次股票了，也有可能是在今天才卖出第二次股票，取这两种情况最大值，收益为dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]
• 最后dp[prices.length-1]表示最终买卖一次股票的收益，dp[prices.length-1]表示最终买卖两次股票的收益

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
 */
function maxProfit( prices ) {
    // write code here
    // 0表示第i天都从未买过股票的收益，
    // 1表示第i天买过一次股票但是没有卖出的收益，
    // 2表示第i天买过一次股票也卖过一次的收益，
    // 3表示第i天买过两次股票但只卖出一次的收益，
    // 4表示第i天买过两次股票并且卖出两次的收益。
    // 因为可能有负收益，所以要初始化为最小值。
    const dp = Array.from(new Array(prices.length), () => new Array(5).fill(-Infinity));  
    dp[0][0] = 0;  // 第一天不买入的收益
    dp[0][1] = -prices[0];  // 第一天买入的收益

    for (let i = 1; i < prices.length; ++i) {
        dp[i][0] = dp[i-1][0];  // 都是0，但是初始为-Infinity所以要更新
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]-prices[i]);
        dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1]+prices[i]);
        dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2]-prices[i]);
        dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3]+prices[i]);
    }

    return Math.max(dp[prices.length-1][2], dp[prices.length-1][4]);
}
module.exports = {
    maxProfit : maxProfit
};