Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]Understand the problem:
https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations
1. Define States
To represent the decision at index i:
buy[i]
: Max profit till index i. The series of transaction is ending with a buy.sell[i]
: Max profit till index i. The series of transaction is ending with a sell.
To clarify:
- Till index
i
, the buy / sell action must happen and must be the last action. It may not happen at indexi
. It may happen ati - 1, i - 2, ... 0
. - In the end
n - 1
, returnsell[n - 1]
. Apparently we cannot finally end up with a buy. In that case, we would rather take a rest atn - 1
. - For special case no transaction at all, classify it as
sell[i]
, so that in the end, we can still returnsell[n - 1]
. Thanks @alex153 @kennethliaoke @anshu2.
2. Define Recursion
buy[i]
: To make a decision whether to buy ati
, we either take a rest, by just using the old decision ati - 1
, or sell at/beforei - 2
, then buy ati
, We cannot sell ati - 1
, then buy ati
, because of cooldown.sell[i]
: To make a decision whether to sell ati
, we either take a rest, by just using the old decision ati - 1
, or buy at/beforei - 1
, then sell ati
.
So we get the following formula:
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
3. Optimize to O(1) Space
DP solution only depending on
i - 1
and i - 2
can be optimized using O(1) space.- Let
b2, b1, b0
representbuy[i - 2], buy[i - 1], buy[i]
- Let
s2, s1, s0
representsell[i - 2], sell[i - 1], sell[i]
Then arrays turn into Fibonacci like recursion:
b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);
4. Write Code in 5 Minutes
First we define the initial states at
i = 0
:- We can buy. The max profit at
i = 0
ending with a buy is-prices[0]
. - We cannot sell. The max profit at
i = 0
ending with a sell is0
.
Code (Java):
public class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) { return 0; } int b1 = -prices[0]; int s2 = 0; int s1 = 0; for (int i = 1; i <= prices.length; i++) { int b0 = Math.max(b1, s2 - prices[i - 1]); int s0 = Math.max(s1, b1 + prices[i - 1]); b1 = b0; s2 = s1; s1 = s0; } return s1; } }
Update on 10/25/18:
class Solution { public int maxProfit(int[] prices) { if (prices == null || prices.length < 2) { return 0; } int prevHold = -prices[0]; int prevSold = 0; int prevRest = 0; for (int i = 1; i < prices.length; i++) { int currHold = Math.max(prevRest - prices[i], prevHold); int currSold = prevHold + prices[i]; int currRest = Math.max(prevRest, prevSold); prevHold = currHold; prevSold = currSold; prevRest = currRest; } return Math.max(prevSold, prevRest); } }
This comment has been removed by the author.
ReplyDeletewhat is n here? prices.length?
ReplyDeleteBest explanation ever! Started with normal approach and optimized Space by considering the Dependency DAG! Nice work! Keep it UP!
ReplyDeleteyo oo
ReplyDeleteGr8 explanation
ReplyDeleteWww.daybyday.in
ReplyDeleteWww.daybyday.in
ReplyDeleteWith a small tweak, the recursive relationship can be used on Problem 714.
ReplyDeleteI accept there are numerous more pleasurable open doors ahead for people that took a gander at your site.nominee services in dubai
ReplyDelete