动态规划三要素

  1. 状态数组含义
  2. 初始化含义
  3. 状态转移方程
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 两次交易所能获得的最大收益
 * @param prices int整型一维数组 股票每一天的价格
 * @return int整型
 */
function maxProfit( prices ) {
    // write code here
    const n = prices.length;
    if(!prices.length)    return 0;
    // 1、 状态数组
    // 每层，可能的五种状态
    // 0. 未买入第一次，未买入第二次
    // 1. 买入第一次，未买入第二次
    // 2. 卖出第一次，未买入第二次
    // 3. 卖出第一次，买入第二次
    // 4. 卖出第一次，卖出第二次
    const dp = new Array(n).fill(0).map(() => new Array(5).fill(-Infinity));// 初始化时我们给一个比较小的数，这样 max 比较时，会选择更大的数，可以少点判断
    // 2、 用第一天的状态初始化
    // 第一天的状态只可能有两种
    dp[0][0] = 0;            // 未买入第一次，当前最高收益 0
    dp[0][1] = -prices[0];    // 买入第一次，当前最高收益就是买入后剩的钱，因为初始时是没钱的，所以直接为负值
    for(let i = 1; i < n; i++) {
      	// 3、 状态转移方程
        dp[i][0] = dp[i - 1][0];    // 保持未买入
        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[n - 1][4], Math.max(0, dp[n - 1][2]))    //有可能第二次是没必要买的，第一次买完后
}
module.exports = {
    maxProfit : maxProfit
};