0123. Best Time to Buy and Sell Stock III
Hard | Array + DP | 1272 ms (50.09%), 28.3 MB (46.16%)
Source: LeetCode - Best Time to Buy and Sell Stock III GitHub: Solution / Performance
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).
Constraints:
1 <= prices.length <= 10^50 <= prices[i] <= 10^5
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.
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.
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Input: prices = [1]
Output: 0Note that this problem limits us to have at most two transactions, so we need to maintain an array with the size "2+1" (one for day 0 initialization) to record MAX profit among one or two transactions.
Keep in mind that a complete transaction means "Buy + Sell". In other words, buying new stock equals creating a new transaction. Thus, when we calculate the hold state's profit with i transactions, for buying stock, we need to take the no-hold state's profit with "i-1" transaction.
Hold state means you hold the stock.
Since you don't have any stocks at the beginning, the profit at this state is initialized with negative infinity.
The profit in this state is calculated by:
previous no-hold state's profit - current stock price (= buy) = no-hold state's profit w/ 'i-1' transactions - cur. stock price
No-Hold state means you do not hold any stocks.
Since you don't have any stocks at the beginning (you're initially at this state ), the profit at this state is initialized with 0.
The profit in this state is calculated by:
previous hold state's profit + current stock price (= sell) = hold state's profit w/ 'i' transactions + cur. stock priceReturn the profit at the no-hold state as the maximum profit since the hold state still has stock on hold.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# (base case)
if len(prices) == 0 or len(prices) == 1: return 0
# ==================================================
# Array + Dynamic Programming (FSM) =
# ==================================================
# time : O(n)
# space : O(1)
# '+1' for day 0 initialization
T = 2 + 1
hold, noHold = [float('-inf')] * T, [0] * T
for price in prices:
for i in range(1, T):
preHold, preNoHold = hold[i], noHold[i]
hold[i] = max(preHold, noHold[i-1] - price)
noHold[i] = max(preNoHold, preHold + price)
return noHold[-1]class Solution {
/**
* @time : O(n)
* @space : O(1)
*/
public int maxProfit(int[] prices) {
/* base case */
if(prices.length == 0 || prices.length == 1) return 0;
int T = 2 + 1;
int[] hold = new int[T], noHold = new int[T];
Arrays.fill(hold, Integer.MIN_VALUE);
Arrays.fill(noHold, 0);
for(int price: prices) {
for(int i=1 ; i<T ; i++) {
int preHold = hold[i], preNoHold = noHold[i];
hold[i] = Math.max(preHold, noHold[i-1] - price);
noHold[i] = Math.max(preNoHold, preHold + price);
}
}
return noHold[T - 1];
}
}Last updated
Was this helpful?