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).
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.
Constraints:
1 <= prices.length <= 1050 <= prices[i] <= 10
Java Solution
To solve this problem, you can use dynamic programming to keep track of the maximum profit for each possible state. Here’s a Java solution:
public class BuySellStockIII {
public static int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int n = prices.length;
int[][] dp = new int[n][5];
// Initialize the first day
dp[0][1] = -prices[0];
dp[0][3] = Integer.MIN_VALUE;
// Iterate through each day and update the dp array
for (int i = 1; i < n; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
// The maximum profit is in one of the last two states
return Math.max(dp[n - 1][2], dp[n - 1][4]);
}
public static void main(String[] args) {
int[] prices1 = {3, 3, 5, 0, 0, 3, 1, 4};
System.out.println(maxProfit(prices1)); // Output: 6
int[] prices2 = {1, 2, 3, 4, 5};
System.out.println(maxProfit(prices2)); // Output: 4
int[] prices3 = {7, 6, 4, 3, 1};
System.out.println(maxProfit(prices3)); // Output: 0
}
}
This Java code uses a 2D array dp to represent the maximum profit at each state. The states are represented by indices 1 to 4, where state 1 represents buying for the first time, state 2 represents selling for the first time, state 3 represents buying for the second time, and state 4 represents selling for the second time. The final result is the maximum profit in either state 2 or state 4.
Python Solution
Here’s the equivalent Python solution for finding the maximum profit with at most two transactions:
def maxProfit(prices):
if not prices or len(prices) == 0:
return 0
n = len(prices)
dp = [[0] * 5 for _ in range(n)]
# Initialize the first day
dp[0][1] = -prices[0]
dp[0][3] = float('-inf')
# Iterate through each day and update the dp array
for i in range(1, n):
dp[i][1] = max(dp[i - 1][1], -prices[i])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i])
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
# The maximum profit is in one of the last two states
return max(dp[-1][2], dp[-1][4])
# Test cases
prices1 = [3, 3, 5, 0, 0, 3, 1, 4]
print(maxProfit(prices1)) # Output: 6
prices2 = [1, 2, 3, 4, 5]
print(maxProfit(prices2)) # Output: 4
prices3 = [7, 6, 4, 3, 1]
print(maxProfit(prices3)) # Output: 0
This Python code follows the same logic as the Java solution. It uses a 2D array dp to represent the maximum profit at each state. The states are represented by indices 1 to 4, where state 1 represents buying for the first time, state 2 represents selling for the first time, state 3 represents buying for the second time, and state 4 represents selling for the second time. The final result is the maximum profit in either state 2 or state 4.