Problem Statement: Best Time to Buy and Sell Stock III
You are given an integer array prices where prices[i] is the price of a given stock on the i-th day.
You can complete at most two transactions. In other words, you can make at most two buy-sell pairs. Each transaction consists of buying one stock and then selling it. You cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Return the maximum profit you can achieve.
Example:
- Input:
[3,2,6,5,0,3] - Output:
7- Explanation: Buy at day 2 (price = 2), sell at day 3 (price = 6). Profit = 6 – 2 = 4.
- Then buy at day 5 (price = 0), sell at day 6 (price = 3). Profit = 3 – 0 = 3.
- Total profit = 4 + 3 = 7.
- Input:
[1,2,3,4,5] - Output:
4- Explanation: Buy at day 1 (price = 1), sell at day 5 (price = 5). Profit = 5 – 1 = 4.
- Input:
[7,6,4,3,1] - Output:
0- Explanation: No transaction is possible, so the profit is 0.
Approach
To solve this problem, we can use Dynamic Programming (DP) to track the maximum profit we can make with at most two transactions. The key idea is to break the problem into two subproblems:
- First Transaction (buy and sell): We need to track the maximum profit we can make by completing the first transaction on or before day
i. - Second Transaction (buy and sell): We need to track the maximum profit we can make by completing the second transaction on or after day
i.
Dynamic Programming Approach:
- We maintain two arrays:
first[i]: The maximum profit that can be made by completing the first transaction on or before dayi.second[i]: The maximum profit that can be made by completing the second transaction on or after dayi.
- First Transaction:
- As we traverse through the list of prices, we keep track of the minimum price observed so far and calculate the maximum profit that could have been obtained by selling at each day’s price.
- Second Transaction:
- We traverse from the end to the beginning of the list. For each price, we calculate the maximum profit for the second transaction using the maximum profit from the second transaction on the next day.
Steps:
- Calculate the profit for the first transaction (
first[]array). - Calculate the profit for the second transaction (
second[]array). - The final result will be the maximum value of
first[i] + second[i]for alli.
Code Implementation
C:
#include <stdio.h>
int maxProfit(int* prices, int pricesSize) {
if (pricesSize == 0) return 0;
int first[pricesSize], second[pricesSize];
int minPrice = prices[0];
first[0] = 0; // no profit on the first day
// Calculate maximum profit with at most one transaction up to day i
for (int i = 1; i < pricesSize; i++) {
first[i] = (prices[i] - minPrice > first[i - 1]) ? prices[i] - minPrice : first[i - 1];
minPrice = (prices[i] < minPrice) ? prices[i] : minPrice;
}
int maxPrice = prices[pricesSize - 1];
second[pricesSize - 1] = 0; // no profit on the last day
// Calculate maximum profit with at most one transaction from day i to end
for (int i = pricesSize - 2; i >= 0; i--) {
second[i] = (maxPrice - prices[i] > second[i + 1]) ? maxPrice - prices[i] : second[i + 1];
maxPrice = (prices[i] > maxPrice) ? prices[i] : maxPrice;
}
int maxProfit = 0;
for (int i = 0; i < pricesSize; i++) {
maxProfit = (first[i] + second[i] > maxProfit) ? first[i] + second[i] : maxProfit;
}
return maxProfit;
}
int main() {
int prices[] = {3,2,6,5,0,3};
int pricesSize = sizeof(prices) / sizeof(prices[0]);
printf("Max profit: %d\n", maxProfit(prices, pricesSize)); // Output: 7
return 0;
}
C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0;
vector<int> first(n, 0), second(n, 0);
int minPrice = prices[0];
// Calculate maximum profit for the first transaction up to each day
for (int i = 1; i < n; i++) {
first[i] = max(first[i - 1], prices[i] - minPrice);
minPrice = min(minPrice, prices[i]);
}
int maxPrice = prices[n - 1];
// Calculate maximum profit for the second transaction from each day
for (int i = n - 2; i >= 0; i--) {
second[i] = max(second[i + 1], maxPrice - prices[i]);
maxPrice = max(maxPrice, prices[i]);
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = max(maxProfit, first[i] + second[i]);
}
return maxProfit;
}
int main() {
vector<int> prices = {3,2,6,5,0,3};
cout << "Max profit: " << maxProfit(prices) << endl; // Output: 7
return 0;
}
Java:
public class BestTimeToBuyAndSellStockIII {
public static int maxProfit(int[] prices) {
int n = prices.length;
if (n == 0) return 0;
int[] first = new int[n];
int[] second = new int[n];
// First transaction: calculate max profit up to each day
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
first[i] = Math.max(first[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
// Second transaction: calculate max profit from each day to the end
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
second[i] = Math.max(second[i + 1], maxPrice - prices[i]);
maxPrice = Math.max(maxPrice, prices[i]);
}
// Max profit by combining both transactions
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = Math.max(maxProfit, first[i] + second[i]);
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {3, 2, 6, 5, 0, 3};
System.out.println("Max profit: " + maxProfit(prices)); // Output: 7
}
}
Python:
def maxProfit(prices):
n = len(prices)
if n == 0:
return 0
first = [0] * n
second = [0] * n
# First transaction: calculate max profit up to each day
min_price = prices[0]
for i in range(1, n):
first[i] = max(first[i - 1], prices[i] - min_price)
min_price = min(min_price, prices[i])
# Second transaction: calculate max profit from each day to the end
max_price = prices[-1]
for i in range(n - 2, -1, -1):
second[i] = max(second[i + 1], max_price - prices[i])
max_price = max(max_price, prices[i])
# Max profit by combining both transactions
max_profit = 0
for i in range(n):
max_profit = max(max_profit, first[i] + second[i])
return max_profit
# Example usage
prices = [3, 2, 6, 5, 0, 3]
print("Max profit:", maxProfit(prices)) # Output: 7
C#:
using System;
public class BestTimeToBuyAndSellStockIII {
public static int MaxProfit(int[] prices) {
int n = prices.Length;
if (n == 0) return 0;
int[] first = new int[n];
int[] second = new int[n];
// First transaction: calculate max profit up to each day
int minPrice = prices[0];
for (int i = 1; i < n; i++) {
first[i] = Math.Max(first[i - 1], prices[i] - minPrice);
minPrice = Math.Min(minPrice, prices[i]);
}
// Second transaction: calculate max profit from each day to the end
int maxPrice = prices[n - 1];
for (int i = n - 2; i >= 0; i--) {
second[i] = Math.Max(second[i + 1], maxPrice - prices[i]);
maxPrice = Math.Max(maxPrice, prices[i]);
}
// Max profit by combining both transactions
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = Math.Max(maxProfit, first[i] + second[i]);
}
return maxProfit;
}
static void Main() {
int[] prices = {3, 2, 6, 5, 0, 3};
Console.WriteLine("Max profit: " + MaxProfit(prices)); // Output: 7
}
}
JavaScript:
function maxProfit(prices) {
const n = prices.length;
if (n === 0) return 0;
let first = Array(n).fill(0);
let second = Array(n).fill(0);
// First transaction: calculate max profit up to each day
let minPrice = prices[0];
for (let i = 1; i < n; i++) {
first[i] = Math.max(first[i - 1], prices[i] - minPrice);
minPrice = Math.min(minPrice, prices[i]);
}
// Second transaction: calculate max profit from each day to the end
let maxPrice = prices[n - 1];
for (let i = n - 2; i >= 0; i--) {
second[i] = Math.max(second[i + 1], maxPrice - prices[i]);
maxPrice = Math.max(maxPrice, prices[i]);
}
// Max profit by combining both transactions
let maxProfit = 0;
for (let i = 0; i < n; i++) {
maxProfit = Math.max(maxProfit, first[i] + second[i]);
}
return maxProfit;
}
// Example usage
let prices = [3, 2, 6, 5, 0, 3];
console.log("Max profit:", maxProfit(prices)); // Output: 7
Explanation:
- Dynamic Programming Arrays:
first[i]stores the maximum profit you can make by completing the first transaction on or before dayi.second[i]stores the maximum profit you can make by completing the second transaction on or after dayi.
- Steps:
- First, calculate the maximum profit for the first transaction using
first[]. - Then, calculate the maximum profit for the second transaction using
second[]starting from the end of the array. - Finally, combine the two to get the total maximum profit by adding the values of
first[i]andsecond[i]at each indexi.
- First, calculate the maximum profit for the first transaction using
Time Complexity:
- O(n) where
nis the number of days (prices). We make two passes through the array (one forfirst[]and one forsecond[]).
Space Complexity:
- O(n) due to the storage of the
first[]andsecond[]arrays.
Summary:
This problem can be efficiently solved using dynamic programming. The key idea is to compute the maximum profit you can make with two transactions using two separate passes through the prices array. This approach has a linear time complexity and is space efficient if we only store necessary information.