123. 买卖股票的最佳时机 III
题目描述
输入数组 prices，第 i 个元素是某支股票第 i 天的价格。
一次交易指买入一股再卖出。你最多可以完成两次交易，也可以只做一次或不做。
不能同时持有多股：再次买入之前，必须先卖出手上的股票。返回能获得的最大利润。
示例 1
输入：prices = [3,3,5,0,0,3,1,4] 输出：6
解释：价格 0 买、3 卖赚 3，再 1 买、4 卖赚 3，共 6。
示例 2
输入：prices = [1,2,3,4,5] 输出：4
解释：一次交易从 1 买到 5 卖即可赚 4；不能连续两天买入后再一起卖出。
示例 3
输入：prices = [7,6,4,3,1] 输出：0
解释：价格一直下跌，不交易，利润为 0。
数据范围
1 <= prices.length <= 10^50 <= prices[i] <= 10^5
解题思路：四状态动态规划
用四个状态表示到今天为止的最好结果：buy1 = 第一次买入后的最大余额，sell1 = 第一次卖出后，buy2 = 第二次买入后，sell2 = 第二次卖出后。每天依次更新：buy1 = max(buy1, -p)，sell1 = max(sell1, buy1+p)，buy2 = max(buy2, sell1-p)，sell2 = max(sell2, buy2+p)。
为什么正确
每个状态要么保持昨天的值（今天不操作），要么由前一个状态今天操作一次得到。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
同一天内按 buy1→sell1→buy2→sell2 顺序用新值更新是安全的：同一天买了又卖的利润为 0，不会多算。答案是 sell2，它已经覆盖了只交易一次和不交易的情况。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
buy1 = buy2 = -prices[0]
sell1 = sell2 = 0
for p in prices[1:]:
buy1 = max(buy1, -p)
sell1 = max(sell1, buy1 + p)
buy2 = max(buy2, sell1 - p)
sell2 = max(sell2, buy2 + p)
return sell2class Solution {
public int maxProfit(int[] prices) {
int buy1 = -prices[0], buy2 = -prices[0];
int sell1 = 0, sell2 = 0;
for (int i = 1; i < prices.length; i++) {
int p = prices[i];
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p);
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int buy1 = -prices[0], buy2 = -prices[0];
int sell1 = 0, sell2 = 0;
for (int i = 1; i < (int)prices.size(); i++) {
int p = prices[i];
buy1 = max(buy1, -p);
sell1 = max(sell1, buy1 + p);
buy2 = max(buy2, sell1 - p);
sell2 = max(sell2, buy2 + p);
}
return sell2;
}
};func maxProfit(prices []int) int {
buy1, buy2 := -prices[0], -prices[0]
sell1, sell2 := 0, 0
for _, p := range prices[1:] {
buy1 = max(buy1, -p)
sell1 = max(sell1, buy1+p)
buy2 = max(buy2, sell1-p)
sell2 = max(sell2, buy2+p)
}
return sell2
}var maxProfit = function(prices) {
let buy1 = -prices[0], buy2 = -prices[0];
let sell1 = 0, sell2 = 0;
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p);
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
};function maxProfit(prices: number[]): number {
let buy1 = -prices[0], buy2 = -prices[0];
let sell1 = 0, sell2 = 0;
for (let i = 1; i < prices.length; i++) {
const p = prices[i];
buy1 = Math.max(buy1, -p);
sell1 = Math.max(sell1, buy1 + p);
buy2 = Math.max(buy2, sell1 - p);
sell2 = Math.max(sell2, buy2 + p);
}
return sell2;
}其他解法
四状态动态规划只用 O(1) 空间且可推广到 k 次交易；前后缀分割用 O(n) 空间，但思路更直观。
解法 2：前后缀分割 时间 O(n)，空间 O(n)
两次交易可以按某一天 i 分成前后两段，每段各做一次交易。从左到右扫描，维护最低价，得到 left[i]：prices[0..i] 内一次交易的最大利润。再从右到左扫描，维护最高价，得到 prices[i..n-1] 内的最大利润 right。答案是 left[i] + right 的最大值。
把问题拆成两个 121 题，容易理解和证明。需要 O(n) 数组，且只适用于恰好两次交易，不易推广到 k 次。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
left = [0] * n
low = prices[0]
for i in range(1, n):
low = min(low, prices[i])
left[i] = max(left[i - 1], prices[i] - low)
best = 0
high = prices[-1]
right = 0
for i in range(n - 1, -1, -1):
high = max(high, prices[i])
right = max(right, high - prices[i])
best = max(best, left[i] + right)
return bestclass Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[] left = new int[n];
int low = prices[0];
for (int i = 1; i < n; i++) {
low = Math.min(low, prices[i]);
left[i] = Math.max(left[i - 1], prices[i] - low);
}
int best = 0, high = prices[n - 1], right = 0;
for (int i = n - 1; i >= 0; i--) {
high = Math.max(high, prices[i]);
right = Math.max(right, high - prices[i]);
best = Math.max(best, left[i] + right);
}
return best;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<int> left(n, 0);
int low = prices[0];
for (int i = 1; i < n; i++) {
low = min(low, prices[i]);
left[i] = max(left[i - 1], prices[i] - low);
}
int best = 0, high = prices[n - 1], right = 0;
for (int i = n - 1; i >= 0; i--) {
high = max(high, prices[i]);
right = max(right, high - prices[i]);
best = max(best, left[i] + right);
}
return best;
}
};func maxProfit(prices []int) int {
n := len(prices)
left := make([]int, n)
low := prices[0]
for i := 1; i < n; i++ {
low = min(low, prices[i])
left[i] = max(left[i-1], prices[i]-low)
}
best, high, right := 0, prices[n-1], 0
for i := n - 1; i >= 0; i-- {
high = max(high, prices[i])
right = max(right, high-prices[i])
best = max(best, left[i]+right)
}
return best
}var maxProfit = function(prices) {
const n = prices.length;
const left = new Array(n).fill(0);
let low = prices[0];
for (let i = 1; i < n; i++) {
low = Math.min(low, prices[i]);
left[i] = Math.max(left[i - 1], prices[i] - low);
}
let best = 0, high = prices[n - 1], right = 0;
for (let i = n - 1; i >= 0; i--) {
high = Math.max(high, prices[i]);
right = Math.max(right, high - prices[i]);
best = Math.max(best, left[i] + right);
}
return best;
};function maxProfit(prices: number[]): number {
const n = prices.length;
const left: number[] = new Array(n).fill(0);
let low = prices[0];
for (let i = 1; i < n; i++) {
low = Math.min(low, prices[i]);
left[i] = Math.max(left[i - 1], prices[i] - low);
}
let best = 0, high = prices[n - 1], right = 0;
for (let i = n - 1; i >= 0; i--) {
high = Math.max(high, prices[i]);
right = Math.max(right, high - prices[i]);
best = Math.max(best, left[i] + right);
}
return best;
}