class Solution {
public:
int maxProfit(vector<int>& prices) {
}
};
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4] 输出：6 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。 随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5] 输出：4 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
示例 4：
输入：prices = [1] 输出：0
提示：
1 <= prices.length <= 1050 <= prices[i] <= 105原站题解
rust 解法, 执行用时: 8 ms, 内存消耗: 3.4 MB, 提交时间: 2023-10-03 10:42:57
impl Solution {
pub fn max_profit(prices: Vec<i32>) -> i32 {
let (mut buy0, mut sell0) = (-prices[0], 0);
let (mut buy1, mut sell1) = (-prices[0], 0);
prices.iter().skip(1).for_each(|&v| {
buy0 = buy0.max(-v);
sell0 = sell0.max(v + buy0);
buy1 = buy1.max(sell0 - v);
sell1 = sell1.max(v + buy1);
});
sell1
}
}
php 解法, 执行用时: 264 ms, 内存消耗: 31.3 MB, 提交时间: 2023-10-03 10:42:36
class Solution {
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit2($prices) {
if (empty($prices)) return 0;
$dp = [];
$deal_count = 2;
for ($i = 0; $i < count($prices); $i++) {
for ($j = $deal_count; $j >= 1; $j--) {
if ($i == 0) {
$dp[$i][$j][0] = 0;
$dp[$i][$j][1] = -$prices[$i];
continue;
}
$dp[$i][$j][0] = max($dp[$i - 1][$j][0], $dp[$i - 1][$j][1] + $prices[$i]);
$dp[$i][$j][1] = max($dp[$i - 1][$j][1], $dp[$i - 1][$j - 1][0] - $prices[$i]);
}
}
return $dp[count($prices) - 1][$deal_count][0];
}
/**
* @param Integer[] $prices
* @return Integer
*/
function maxProfit($prices) {
$one_buy = $two_buy = PHP_INT_MIN;
$one_sell = $two_sell = 0;
foreach ($prices as $price) {
$one_buy = max($one_buy, -$price);
$one_sell = max($one_sell, $one_buy + $price);
$two_buy = max($two_buy, $one_sell - $price);
$two_sell = max($two_sell, $two_buy + $price);
}
return $two_sell;
}
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 50.7 MB, 提交时间: 2023-09-21 14:57:35
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
const n = prices.length;
let buy1 = -prices[0], buy2 = -prices[0];
let sell1 = 0, sell2 = 0;
for (let i = 1; i < n; i++) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
};
golang 解法, 执行用时: 140 ms, 内存消耗: 8.4 MB, 提交时间: 2023-09-21 14:57:23
func maxProfit(prices []int) int {
buy1, sell1 := -prices[0], 0
buy2, sell2 := -prices[0], 0
for i := 1; i < len(prices); i++ {
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1+prices[i])
buy2 = max(buy2, sell1-prices[i])
sell2 = max(sell2, buy2+prices[i])
}
return sell2
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
python3 解法, 执行用时: 316 ms, 内存消耗: 26.9 MB, 提交时间: 2023-09-21 14:56:52
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
buy1, sell1 = -prices[0], 0
buy2, sell2 = -prices[0], 0
for i in range(1, n):
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2, buy2 + prices[i])
return sell2
java 解法, 执行用时: 2 ms, 内存消耗: 54.6 MB, 提交时间: 2023-09-21 14:55:26
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < n; ++i) {
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1 + prices[i]);
buy2 = Math.max(buy2, sell1 - prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 73.9 MB, 提交时间: 2023-09-21 14:55:11
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int buy1 = -prices[0], sell1 = 0;
int buy2 = -prices[0], sell2 = 0;
for (int i = 1; i < n; ++i) {
buy1 = max(buy1, -prices[i]);
sell1 = max(sell1, buy1 + prices[i]);
buy2 = max(buy2, sell1 - prices[i]);
sell2 = max(sell2, buy2 + prices[i]);
}
return sell2;
}
};
python3 解法, 执行用时: 748 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-21 14:53:29
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 甲：这n天怎样买股票赚的多-------------------------------------
n = len(prices)
# 乙：dp[i]代表第i天-------------------------------------------
# 乙：dp[i][0]代表第i天过后第一次买股票时的最大收益
# 乙：总之，今天过后我必有股票在手上，要么之前买的，要么今天买的
# 乙：dp[i][1]代表第i天过后第一次卖股票时的最大收益
# 乙：总之，今天过后我手上空空如也，要么本来就没有，有我也给卖了
# 乙：dp[i][2]代表第i天过后第二次买股票时的最大收益
# 乙：dp[i][3]代表第i天过后第二次卖股票时的最大收益
dp = [[0,0,0,0] for _ in range(n)]
# 乙： 今天是第一天---------------------------------------------
# 乙： 第一次买股票是吧，prices[0]块钱拿去，今天股票我买了
# 乙： 第一次卖股票是吧，prices[0]块钱买来又卖掉，血赚0元
# 乙： 第二次买，我买了又卖掉又买回来，花费prices[0]块钱
# 乙： 第二次买，我买了又卖掉又买回来又卖掉，哎，就是玩
# 注： 在同一天内反复买卖是不影响最终结果的，因为反正都是0
dp[0]=[-prices[0],0,-prices[0],0]
# 旁白： 时间一天天过去
for i in range(1, n):
# 甲： 今天是第i天，如果我第一次买股票，该怎么操作------
# 乙： dp[i-1][0] 今天的股票太贵了，买之前的股票更划算
# 乙： - prices[i] 今天的股票更便宜，我买了，prices[i]块钱拿去
dp[i][0] = max(dp[i-1][0], -prices[i])
# 甲： 今天是第i天，如果我第一次卖股票，该怎么操作------
# 乙： dp[i-1][1] 今天股市不行，还是之前卖更划算
# 乙： + prices[i] + dp[i-1][0] 今天的行情不错，股票卖掉，血赚prices[i]块钱，
# dp[i-1][0]是我用低价买入花的钱
dp[i][1] = max(dp[i-1][1], + prices[i] + dp[i-1][0])
# 甲： 今天是第i天，如果我第二次买股票，该怎么操作------
# 乙： dp[i-1][0] 今天的股票太贵了，买之前的股票更划算
# 乙： - prices[i] 今天的股票更便宜，我买了，prices[i]块钱拿去
# dp[i-1][1]是我第一次卖股票赚的钱
dp[i][2] = max(dp[i-1][2], - prices[i] + dp[i-1][1])
# 甲： 今天是第i天，如果我第一次卖股票，该怎么操作------
# 乙： dp[i-1][1] 今天股市不行，还是之前卖更划算
# 乙： + prices[i] + dp[i-1][0] 今天的行情不错，股票卖掉，血赚prices[i]块钱，
# dp[i-1][2]是我第二次买完股票后的最大收益
dp[i][3] = max(dp[i-1][3], + prices[i] + dp[i-1][2])
return dp[-1][-1]