122. 买卖股票的最佳时机 II
题目描述
输入数组 prices，prices[i] 是某支股票第 i 天的价格。
每天都可以选择买入、卖出或不操作，交易次数不限。但手上同一时刻最多只能有一股。同一天可以先卖出再买入。
返回能获得的最大总利润。
示例 1
输入：prices = [7,1,5,3,6,4] 输出：7
解释：价格 1 买、5 卖赚 4，再 3 买、6 卖赚 3，共 7。
示例 2
输入：prices = [1,2,3,4,5] 输出：4
解释：第一天买入、最后一天卖出，赚 4。
示例 3
输入：prices = [7,6,4,3,1] 输出：0
解释：价格一直下跌，不交易，利润为 0。
数据范围
1 <= prices.length <= 3 * 10^40 <= prices[i] <= 10^4
解题思路：贪心累加上涨差价
交易次数不限，可以把任何一段上涨拆成相邻两天的上涨之和：prices[j] - prices[i] = Σ(prices[k] - prices[k-1])。所以只要把所有正的单日涨幅加起来即可，下跌的那天不持有。
为什么正确
处理到第 i 天时，profit 是前 i 天所有正涨幅之和，也就是前 i 天的最大利润。
复杂度分析
时间 O(n)，空间 O(1)。
易错点
累加涨幅不等于真实的买卖操作，只是利润相同：连续上涨 1→2→3 赚 2，等价于 1 买 3 卖。不要和 121 题（只能交易一次）混淆。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitclass Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < (int)prices.size(); i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
};func maxProfit(prices []int) int {
profit := 0
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
profit += prices[i] - prices[i-1]
}
}
return profit
}var maxProfit = function(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
};function maxProfit(prices: number[]): number {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}其他解法
两种解法都是 O(n) 时间、O(1) 空间；贪心最简洁，状态机动态规划是股票系列题目的通用模板。
解法 2：持有状态动态规划 时间 O(n)，空间 O(1)
cash 表示当天结束时不持股的最大利润，hold 表示持股的最大利润。初始 cash = 0，hold = -prices[0]。每天用前一天的值更新：cash = max(cash, hold + p)，hold = max(hold, cash - p)。最后返回 cash。
比贪心多想一步，但状态定义可以直接推广到含手续费、冷冻期、限制交易次数的变体。贪心只适用于不限次数且无额外成本的情形。
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
cash, hold = 0, -prices[0]
for p in prices[1:]:
cash, hold = max(cash, hold + p), max(hold, cash - p)
return cashclass Solution {
public int maxProfit(int[] prices) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < prices.length; i++) {
int newCash = Math.max(cash, hold + prices[i]);
int newHold = Math.max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}
}class Solution {
public:
int maxProfit(vector<int>& prices) {
int cash = 0, hold = -prices[0];
for (int i = 1; i < (int)prices.size(); i++) {
int newCash = max(cash, hold + prices[i]);
int newHold = max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}
};func maxProfit(prices []int) int {
cash, hold := 0, -prices[0]
for _, p := range prices[1:] {
cash, hold = max(cash, hold+p), max(hold, cash-p)
}
return cash
}var maxProfit = function(prices) {
let cash = 0, hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
const newCash = Math.max(cash, hold + prices[i]);
const newHold = Math.max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
};function maxProfit(prices: number[]): number {
let cash = 0, hold = -prices[0];
for (let i = 1; i < prices.length; i++) {
const newCash = Math.max(cash, hold + prices[i]);
const newHold = Math.max(hold, cash - prices[i]);
cash = newCash;
hold = newHold;
}
return cash;
}