关于前端:跌妈不认一口气团灭6道股票算法打打气

观感度：🌟🌟🌟🌟🌟

口味：虎皮凤爪

烹饪工夫：10min

我欲清仓归去，又恐迅速反弹，踏空不胜寒。与其储蓄负利，不如厮混其间，少追涨，勿杀跌，夜安眠，不应有恨，获利总在无意间。月有阴晴圆缺，股有横盘涨跌，此事股难全。— 驰名今人白交易

本文已收录在前端食堂同名仓库 Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。

2021 年的基金市场开年至今，暴涨又暴涨。刚迎完财神，期待牛气冲天的年老人们，刚刚入场就狠狠的吃了资本市场的一记重锤。

各种“人类蛊惑行为大赏”轮流演出，让本就魔幻的世界变得更加魔幻。如果你最近也跌了，请点个赞，让咱们相互抱团取暖。

回到 LeetCode 这 6 道股票系列题，其实这 6 道题目能够归为一道题目来看：

1. 交易股票的最佳时机
2. 交易股票的最佳时机 II
3. 交易股票的最佳时机 III
4. 交易股票的最佳时机 IV
5. 最佳交易股票机会含冷冻期
6. 交易股票的最佳时机含手续费

与事实略有不同，题目中增加了一些限度条件，读完题剖析后不难发现。

1. 第一题只交易一次，也就是 k = 1。
2. 第二题不限度交易次数，也就是 k = +infinity。
3. 第三题只交易两次，也就是 k = 2。
4. 第四道限度最多交易次数 k 是任意数。
5. 第五道和第六道不限次数，相当于在第二题的根底上别离增加了交易 冷冻期 和手续费 的额定条件。

咱们每天能做的操作无非是以下这三种：

1. 买入
2. 卖出
3. 无操作

不过要留神以下四点限度条件。

1. 要先买入能力卖出。
2. 题目要求不能同时参加多笔交易，也就是说 再次买入前须要卖出手中持有的股票。
3. 无操作基于两种状态，手中持有股票 和没有持有股票。
4. 交易次数 k 也有限度，只有 k >= 0 时才能够买入。

剖析好了这些状态，接下来就是翻译成代码了。

首先，咱们能够建设一个三维数组来示意下面的这些状态，先来明确一些变量含意。

• i: 天数 范畴是 (0 <= i <= n – 1)
• k: 最大交易次数
• 0: 没有持有股票
• 1: 持有股票
• n: 股票数组长度

dp[i][k][0]
dp[i][k][1]

// 举个🌰
dp[2][2][1] // 明天是第 2 天，手中持有股票，最多还能够进行 2 次交易

咱们最终要求的可取得的最大收益就是 dp[n - 1][k][0]，代表最初一天将股票卖出后的最大收益。(这里卖出肯定比持有收益更大，所以是 [0]，而不是 [1])

接下来，咱们尝试列出状态转移方程。

// 明天手中没有持有股票，有两种可能：// 1. 昨天没有持有，明天抉择不操作。对应: dp[i - 1][k][0]
// 2. 昨天持有，明天卖出了，所以明天没有股票了。对应: dp[i - 1][k][1] + prices[i]
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])


// 明天手中持有股票，有两种可能：// 1. 昨天手中持有股票，明天抉择不操作。对应: dp[i - 1][k][1]
// 2. 昨天没有持有股票，明天买入了。对应: dp[i - 1][k - 1][0] - prices[i]
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

很显然，卖出股票利润减少，买入股票利润缩小。因为每次交易蕴含两次成对的操作，买入和卖出。

所以只有买入的时候须要将 k – 1，那么最大利润就是下面这两种可能性中的最大值。

第一题 k = 1

将状态转移方程套入本题的条件，k = 1，列出状态转移方程。

dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])
// k = 0 时，dp[i - 1][0][0] = 0

察看发现 k 既然都是 1 且不会扭转，也就是说 k 对状态转移曾经没有影响了，咱们能够进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], -prices[i])

对于第 0 天，咱们须要进行初始化：

• 不持有：dp[0][0] = 0
• 持有：dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i])
    }
    return dp[n - 1][0]
}

• 工夫复杂度：O(n)
• 空间复杂度：O(n)

咱们发现在转移的时候，dp[i] 只会从 dp[i - 1] 转移得来，因而第一维能够去掉，空间复杂度优化到 O(1)。

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], -prices[i])
    }
    return dp[0]
}

• 工夫复杂度：O(n)
• 空间复杂度：O(1)

咱们也能够将变量名变得更加敌对一些。

• profit_out：卖出时的利润
• profit_in：买入时的利润

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in,  -prices[i])
    }
    return profit_out
}

• 工夫复杂度：O(n)
• 空间复杂度：O(1)

第二题 k = +infinity

将状态转移方程套入本题的条件，k = +infinity。

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])

咱们发现数组中的 k 同样曾经不会扭转了，也就是说 k 对状态转移曾经没有影响了，能够进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])

对于第 0 天，咱们要给出初始值：

• 不持有：dp[0][0] = 0
• 持有：dp[0][1] = -prices[0] (花了 prices[0] 的钱买入股票)

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0][0] = 0 
    dp[0][1] = -prices[0]
    for (let i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
    }
    return dp[n - 1][0]
}

同样在转移的时候，dp[i] 只会从 dp[i – 1] 转移得来，因而第一维能够去掉，空间复杂度优化到 O(1)。

const maxProfit = function(prices) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {let tmp = dp[0] // 两头变量可省略，因为当天买入卖出不影响后果
        dp[0] = Math.max(dp[0], dp[1] + prices[i])
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

同上题一样，咱们能够将变量名变得更加敌对一些。

const maxProfit = function(prices) {
    let n = prices.length
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < n; i++) {profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

第三题 k = 2

后面两种状况，无论是 k = 1，还是 k = +infinity 的状况下，k 对状态转移方程是没有影响的。

不过当 k = 2 时，k 就对状态转移方程有影响了。列出状态转移方程：

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

这个时候 k 无奈化简，咱们须要应用两次循环对 k 进行穷举。

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

不过因为 k 的取值范畴比拟小，咱们也能够间接将它们全副列举进去。

dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i])
dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i])
dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])
            = Math.max(dp[i - 1][1][1], -prices[i])

有了下面两道题的铺垫，咱们前面几道题就间接写出降维后的解法。

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i10 = 0
    let dp_i11 = -prices[0]
    let dp_i20 = 0
    let dp_i21 = -prices[0]
    for (let i = 1; i < n; i++) {dp_i20 = Math.max(dp_i20, dp_i21 + prices[i])
        dp_i21 = Math.max(dp_i21, dp_i10 - prices[i])
        dp_i10 = Math.max(dp_i10, dp_i11 + prices[i])
        dp_i11 = Math.max(dp_i11, -prices[i])
    }
    return dp_i20
}

同下面一样，咱们能够将变量名变得更加敌对一些。

const maxProfit = function(prices) {let profit_1_in = -prices[0], profit_1_out = 0
    let profit_2_in = -prices[0], profit_2_out = 0
    let n = prices.length
    for (let i = 1; i < n; i++) {profit_2_out = Math.max(profit_2_out, profit_2_in + prices[i])
        profit_2_in = Math.max(profit_2_in, profit_1_out - prices[i])
        profit_1_out = Math.max(profit_1_out, profit_1_in + prices[i])
        profit_1_in = Math.max(profit_1_in, -prices[i])
    }
    return profit_2_out
}

第四题 k 是任意数

一个有收益的交易至多须要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。

如果股票价格数组的长度为 n，则有收益的交易的数量最多为 n / 2（整数除法）。因而 k 的临界值是 n / 2。

如果给定的 k 不小于临界值，即 k >= n / 2，则能够将 k 扩大为正无穷，也就是第二题的状况，如下函数 maxProfit2。

const maxProfit = function(k, prices) {
    let n = prices.length
    const maxProfit2 = function(prices) {
        let profit_out = 0
        let profit_in = -prices[0]
        for (let i = 1; i < n; i++) {profit_out = Math.max(profit_out, profit_in + prices[i])
            profit_in = Math.max(profit_in, profit_out - prices[i])
        }
        return profit_out
    }
    if (k > n / 2) {return maxProfit2(prices)
    }
    let profit = new Array(k)
    // 初始化买入卖出时的利润，将每次交易买入、卖出时的利润放在一个对象中，实现降维
    for (let j = 0; j <= k; j++) {profit[j] = {profit_in: -prices[0],
            profit_out: 0
        }
    }
    for (let i = 0; i < n; i++) {for (let j = 1; j <= k; j++) {profit[j] = {profit_out: Math.max(profit[j].profit_out, profit[j].profit_in + prices[i]), 
                profit_in: Math.max(profit[j].profit_in, profit[j-1].profit_out - prices[i])
            }
        }
    }
    return profit[k].profit_out
}

第五题 k 为正无穷但有冷却工夫

每次卖出之后都要等一天能力持续交易，也就是第 i 天抉择买的时候，要从 i – 2 状态转移。

列出状态转移方程。

dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 2][k - 1][0] - prices[i])
            = Math.max(dp[i - 1][k][1], dp[i - 2][k][0] - prices[i])

k 同样对状态转移曾经没有影响了，能够进一步化简方程。

dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i])

const maxProfit = function(prices) {
    let n = prices.length
    let dp_i0 = 0
    let dp_i1 = -prices[0];
    let dp_pre = 0 // 代表 dp[i-2][0]
    for (let i = 0; i < n; i++) {
        let tmp = dp_i0
        dp_i0 = Math.max(dp_i0, dp_i1 + prices[i])
        dp_i1 = Math.max(dp_i1, dp_pre - prices[i])
        dp_pre = tmp
    }
    return dp_i0
}

同下面一样，咱们能够将变量名变得更加敌对一些。

const maxProfit = function(prices) {
    let n = prices.length
    let profit_in = -prices[0]
    let profit_out = 0
    let profit_freeze = 0
    for (let i = 1; i < n; i++) {
        let temp = profit_out
        profit_out = Math.max(profit_out, profit_in + prices[i])
        profit_in = Math.max(profit_in, profit_freeze - prices[i])
        profit_freeze = temp
    }
    return profit_out
}

第六题 k 为正无穷但有手续费

在第二题的根底上，增加了手续费。

每次交易要领取手续费，只有把手续费从利润中减去即可，能够列出如下两种方程。

第一种方程：在每次买入股票时扣除手续费

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)

第二种方程：在每次卖出股票时扣除手续费

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])

const maxProfit = function(prices, fee) {
    let n = prices.length
    let dp = Array.from(new Array(n), () => new Array(2))
    dp[0] = 0
    dp[1] = -prices[0]
    for (let i = 1; i < n; i++) {let tmp = dp[0]
        dp[0] = Math.max(dp[0], dp[1] + prices[i] - fee)
        dp[1] = Math.max(dp[1], tmp - prices[i])
    }
    return dp[0]
}

同下面一样，咱们能够将变量名变得更加敌对一些。

const maxProfit = function(prices, fee) {
    let profit_out = 0
    let profit_in = -prices[0]
    for (let i = 1; i < prices.length; i++) {profit_out = Math.max(profit_out, profit_in + prices[i] - fee)
        profit_in = Math.max(profit_in, profit_out - prices[i])
    }
    return profit_out
}

团灭完股票系列算法再来个首尾呼应，讲一讲所谓的投资时钟。

经济分为两个大周期：经济复苏期 和经济衰退期 。联合通胀和流动性的组合，能够分为四个小周期， 消退后期、消退前期、复苏后期以及复苏前期。

不同的经济周期对应着不同的资产和市场格调。任何的资产都有周期性，没有只涨不跌的资产，即使是茅台这样的外围生产资产在不适合的周期里也能均匀回调 30% 以上，即便钢铁这种夕阳产业在适合的周期也能涨个 50%。

搞清楚了当下位于哪个周期，调整资产进行正当的配置，能力不做韭菜。

站在伟人的肩膀上

• 股票问题系列通解（转载翻译）
• 简略 dp，秒懂股票买卖
• 交易股票最佳时机 6 道题解

2021 组团刷题打算

• 前端食堂的 LeetCode 题解仓库

年初立了一个 flag，下面这个仓库在 2021 年写满 100 道前端面试高频题解，目前进度曾经实现了 50%。

如果你也筹备刷或者正在刷 LeetCode，无妨退出前端食堂，一起并肩作战，刷个畅快。

❤️爱心三连击

1. 如果你感觉食堂酒菜还合胃口，就点个赞反对下吧，你的 赞是我最大的能源。

2. 关注公众号前端食堂，吃好每一顿饭！

3. 点赞、评论、转发 === 催更！