Description:
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete at most two transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Examples:
Example 1:
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.Solution in Python:
Python
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
# Initialize variables to store the maximum profit after each transaction
first_buy = float('-inf')
first_sell = 0
second_buy = float('-inf')
second_sell = 0
for price in prices:
# Update first buy - max profit if we buy stock at current price
first_buy = max(first_buy, -price)
# Update first sell - max profit if we sell stock at current price after first buy
first_sell = max(first_sell, first_buy + price)
# Update second buy - max profit if we buy stock at current price after first sell
second_buy = max(second_buy, first_sell - price)
# Update second sell - max profit if we sell stock at current price after second buy
second_sell = max(second_sell, second_buy + price)
# The second sell will have the maximum profit with at most two transactions
return second_sellExplanation
- Initial Checks:
- If the
priceslist is empty, return 0 because no transactions can be made.
- If the
- Variable Initialization:
first_buy: The maximum profit achievable after the first buy. Initialized to negative infinity since we are “buying” stock.first_sell: The maximum profit achievable after the first sell. Initialized to 0 because initially, we haven’t sold any stock.second_buy: The maximum profit achievable after the second buy. Initialized to negative infinity for the same reason asfirst_buy.second_sell: The maximum profit achievable after the second sell. Initialized to 0.
- Iterating through Prices:
- For each price in the
priceslist:- Update
first_buyto be the maximum of the currentfirst_buyor the negative of the current price (-price). This simulates the action of buying the stock. - Update
first_sellto be the maximum of the currentfirst_sellor the sum offirst_buyand the current price (first_buy + price). This simulates selling the stock after the first buy. - Update
second_buyto be the maximum of the currentsecond_buyor the difference betweenfirst_selland the current price (first_sell - price). This simulates buying the stock again after the first sell. - Update
second_sellto be the maximum of the currentsecond_sellor the sum ofsecond_buyand the current price (second_buy + price). This simulates selling the stock after the second buy.
- Update
- For each price in the
- Returning the Result:
- The value of
second_sellwill have the maximum profit achievable with at most two transactions.
- The value of
Constraints
- The function handles arrays with a length between 1 and 100,000.
- Each price in the array is between 0 and 100,000.
This approach efficiently calculates the maximum profit in O(n) time complexity, where n is the length of the prices array.
Solution in Javascript:
JavaScript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
if (prices.length === 0) {
return 0;
}
// Initialize variables to store the maximum profit after each transaction
let firstBuy = Number.NEGATIVE_INFINITY;
let firstSell = 0;
let secondBuy = Number.NEGATIVE_INFINITY;
let secondSell = 0;
// Iterate through the list of prices
for (let price of prices) {
// Update first buy - max profit if we buy stock at current price
firstBuy = Math.max(firstBuy, -price);
// Update first sell - max profit if we sell stock at current price after first buy
firstSell = Math.max(firstSell, firstBuy + price);
// Update second buy - max profit if we buy stock at current price after first sell
secondBuy = Math.max(secondBuy, firstSell - price);
// Update second sell - max profit if we sell stock at current price after second buy
secondSell = Math.max(secondSell, secondBuy + price);
}
// The second sell will have the maximum profit with at most two transactions
return secondSell;
};Solution in Java:
Java
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
// Initialize variables to store the maximum profit after each transaction
int firstBuy = Integer.MIN_VALUE;
int firstSell = 0;
int secondBuy = Integer.MIN_VALUE;
int secondSell = 0;
// Iterate through the list of prices
for (int price : prices) {
// Update first buy - max profit if we buy stock at current price
firstBuy = Math.max(firstBuy, -price);
// Update first sell - max profit if we sell stock at current price after first buy
firstSell = Math.max(firstSell, firstBuy + price);
// Update second buy - max profit if we buy stock at current price after first sell
secondBuy = Math.max(secondBuy, firstSell - price);
// Update second sell - max profit if we sell stock at current price after second buy
secondSell = Math.max(secondSell, secondBuy + price);
}
// The second sell will have the maximum profit with at most two transactions
return secondSell;
}
}Solution in C#:
C#
public class Solution {
public int MaxProfit(int[] prices) {
if (prices.Length == 0) {
return 0;
}
// Initialize variables to store the maximum profit after each transaction
int firstBuy = int.MinValue;
int firstSell = 0;
int secondBuy = int.MinValue;
int secondSell = 0;
// Iterate through the list of prices
foreach (int price in prices) {
// Update first buy - max profit if we buy stock at current price
firstBuy = Math.Max(firstBuy, -price);
// Update first sell - max profit if we sell stock at current price after first buy
firstSell = Math.Max(firstSell, firstBuy + price);
// Update second buy - max profit if we buy stock at current price after first sell
secondBuy = Math.Max(secondBuy, firstSell - price);
// Update second sell - max profit if we sell stock at current price after second buy
secondSell = Math.Max(secondSell, secondBuy + price);
}
// The second sell will have the maximum profit with at most two transactions
return secondSell;
}
}