123. Best Time to Buy and Sell Stock III
給定一個數組 prices，其中 prices[i] 是第 i 天的股票價格。
找到你能達到的最大利潤。你最多可以完成兩筆交易。
注意：你不能同時進行多筆交易（即，你必須在再次購買之前賣出股票）。
範例：
輸入：prices = [3,3,5,0,0,3,1,4] 輸出：6 解釋：在第 4 天（價格 = 0）買入並在第 6 天（價格 = 3）賣出，利潤 = 3 - 0 = 3。 然後在第 7 天（價格 = 1）買入並在第 8 天（價格 = 4）賣出，利潤 = 4 - 1 = 3。
Python
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
# Initialize the variables to track the maximum profit with 1 and 2 transactions
first_buy = float('inf')
first_profit = 0
second_buy = float('inf')
second_profit = 0
for price in prices:
# For the first buy, we are looking for the minimum price to buy the stock
first_buy = min(first_buy, price)
# For the first profit, we are looking for the maximum profit from the first buy
first_profit = max(first_profit, price - first_buy)
# For the second buy, we are looking for the minimum effective price (after first profit)
second_buy = min(second_buy, price - first_profit)
# For the second profit, we are looking for the maximum profit from the second buy
second_profit = max(second_profit, price - second_buy)
return second_profit
30.56MB, 743ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int first_buy = INT_MAX;
int first_profit = 0;
int second_buy = INT_MAX;
int second_profit = 0;
for (int price : prices) {
// Update the first buy to be the minimum price encountered so far
first_buy = min(first_buy, price);
// Update the first profit to be the maximum profit of selling after the first buy
first_profit = max(first_profit, price - first_buy);
// Update the second buy to be the effective minimum price for the second transaction
second_buy = min(second_buy, price - first_profit);
// Update the second profit to be the maximum profit of selling after the second buy
second_profit = max(second_profit, price - second_buy);
}
return second_profit;
}
};
77.68MB, 84ms
Javascript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (prices.length === 0) {
return 0;
}
let firstBuy = Infinity;
let firstProfit = 0;
let secondBuy = Infinity;
let secondProfit = 0;
for (let price of prices) {
// Update the first buy to be the minimum price encountered so far
firstBuy = Math.min(firstBuy, price);
// Update the first profit to be the maximum profit of selling after the first buy
firstProfit = Math.max(firstProfit, price - firstBuy);
// Update the second buy to be the effective minimum price for the second transaction
secondBuy = Math.min(secondBuy, price - firstProfit);
// Update the second profit to be the maximum profit of selling after the second buy
secondProfit = Math.max(secondProfit, price - secondBuy);
}
return secondProfit;
};
60.76MB, 80ms
