Problem Statement
Stock Trader with Two Transactions
You are a stock trader who wants to maximize profit by buying and selling stocks. 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. Total profit is 6.
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 in 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 <= 10^5
- 0 <= prices[i] <= 10^5
Problem Breakdown
To solve this problem, we need to:
- The key insight is to use dynamic programming to track the maximum profit after different states of transactions.
- We need to consider four states: after buying the first stock, after selling the first stock, after buying the second stock, and after selling the second stock.
- For each day, we have the option to either do nothing or perform a transaction (buy or sell), and we want to maximize our profit.
- We can use a one-pass approach to track all states simultaneously.
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Stock Trader with Two Transactions
You are a stock trader who wants to maximize profit by buying and selling stocks. 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:
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. Total profit is 6.
Example 2:
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 in multiple transactions at the same time. You must sell before buying again.
Example 3:
In this case, no transaction is done, i.e., max profit = 0.
Problem Breakdown
Constraints:
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^5
Key Insights:
The key insight is to use dynamic programming to track the maximum profit after different states of transactions.
We need to consider four states: after buying the first stock, after selling the first stock, after buying the second stock, and after selling the second stock.
For each day, we have the option to either do nothing or perform a transaction (buy or sell), and we want to maximize our profit.
We can use a one-pass approach to track all states simultaneously.
Real-World Application
This problem has several practical applications:
Stock Trading
Optimizing trading strategies with a limited number of transactions.
Transaction Planning
Planning financial transactions with constraints on the number of operations.
Portfolio Optimization
Optimizing investment portfolios with limited rebalancing opportunities.