123.买卖股票的最佳时机-iii.md

Problem: 123. 买卖股票的最佳时机 III

[TOC]

思路

参考了官方的题解（官方写的题解中 -prices[0] 没看懂-_-||），改写成了我的理解，感觉会更加容易理解

解题方法

动态规划

想要求出两次交易的最大利润，这里，设第一次、第二次购入价格、卖出价格分别为buy1, buy2, sell1, sell2，则利润的表达式为：profile = sell2 - buy2 + sell1 - buy1。

将改表达式变形，得：profile = sell2 - (buy2 - (sell1 - buy1))。

若要获取profile的最大值，则第二次购入后的成本offset = buy2 - (sell1 - buy1)必须为最小值。 进一步分析，可知单次卖出的最大利润profile1 = sell1 - buy1必须为最大值，这一步就是查找单次股票最大利润，即buy1必须为最小值，sell2必须为最大值，而buy2必须为sell1之后的最大值。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

function maxProfit(prices: number[]): number {
    const n = prices.length;
    let min = prices[0]
    let offset = prices[0]
    let profile1 = 0, profile2 = 0
    for (let i = 1; i < n; i++) {
        min = Math.min(min, prices[i])
        profile1 = Math.max(profile1, prices[i] - min)
        offset = Math.min(offset, prices[i] - profile1)
        profile2 = Math.max(profile2, prices[i] - offset)
    }
    return profile2
};