LC 0121 0122 0714 0309 0123 0188 [E] [E] [M] [M] [H] [H] Best Time to Buy and Sell Stock I, II, Transaction Fee, Cooldown, III, IV - ALawliet/algorithms GitHub Wiki
think in terms of
i = price index
k = num transactions
T[i][k][0] = if we hold 0 by EOD
T[i][k][1] = if we hold 1 by EOD
I: k = 1
max subarray = Kadane's algorithm, buy low sell high
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
min_price = float('inf')
for price in prices:
min_price = min(min_price, price) # buy lowest
profit = price - min_price
max_profit = max(max_profit, profit) # sell highest
return max_profit
class Solution:
def maxProfit(self, prices: List[int]) -> int:
T_i10 = 0
T_i11 = -math.inf
for price in prices:
T_i10 = max(T_i10, T_i11 + price) # have 0, from rest or sell previously bought
T_i11 = max(T_i11, 0 - price) # have 1, from rest or buy
return T_i10
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1 # low, high
maxP = 0
while r < len(prices):
if prices[l] < prices[r]:
profit = prices[r] - prices[l]
maxP = max(maxP, profit)
else:
l = r
r += 1
return maxP
II: k = inf
greedy post-dictive error, buy if price today was greater than yesterday else don't
class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
max_profit += prices[i] - prices[i-1]
return max_profit
class Solution:
def maxProfit(self, prices: List[int]) -> int:
T_ik0 = 0
T_ik1 = -math.inf
for price in prices:
T_ik0_old = T_ik0 # store prev hold/sell max T[i-1][k][0]
T_ik0 = max(T_ik0, T_ik1 + price) # hold, prev buy + sell at this price
T_ik1 = max(T_ik1, T_ik0_old - price) # hold, prev hold/sell max + buy more at this price
return T_ik0
transaction fee
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
cash = 0
hold = -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee) # sell and complete transaction for a fee
hold = max(hold, cash - prices[i]) # buy and hold
return cash
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
T_ik0 = 0
T_ik1 = -math.inf
for price in prices:
T_ik0_old = T_ik0
T_ik0 = max(T_ik0, T_ik1 + price - fee) # just like #2 but include the fee
T_ik1 = max(T_ik1, T_ik0_old - price)
return T_ik0
cooldown
draw a decision tree
class Solution:
def maxProfit(self, prices: List[int]) -> int:
sold = float('-inf')
held = float('-inf')
reset = 0
for price in prices:
pre_sold = sold
sold = held + price # sell
held = max(held, reset - price) # buy
reset = max(reset, pre_sold) # rest
return max(sold, reset)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# O(n), O(n)
# State: Buying or Selling?
# If Buy -> i + 1
# If Sell -> i + 2 (includes +1 cooldown)
# If Cooldown -> i + 1
dp = {} # key=(i, canbuy) val=max_profit
def dfs(i, canbuy):
if i >= len(prices):
return 0
if (i, canbuy) in dp:
return dp[(i, canbuy)]
cooldown = dfs(i + 1, canbuy) # we have a choice of cooldown at every decision
if canbuy:
buy = dfs(i + 1, False) - prices[i] # we can't buy again right after buying, we have to sell
dp[(i, canbuy)] = max(buy, cooldown)
else:
sell = dfs(i + 2, True) + prices[i] # we can buy again after we sell +1 cooldown
dp[(i, canbuy)] = max(sell, cooldown)
return dp[(i, canbuy)]
return dfs(0, True) # we can buy on the first day
class Solution:
def maxProfit(self, prices: List[int]) -> int:
T_ik0_pre = 0
T_ik0 = 0
T_ik1 = -math.inf
for price in prices:
T_ik0_old = T_ik0 # T[i-1][k][0]
T_ik0 = max(T_ik0, T_ik1 + price)
T_ik1 = max(T_ik1, T_ik0_pre - price) # T[i-2][k][0] instead of T[i-1][k][0]
T_ik0_pre = T_ik0_old # T[i-2][k][0]
return T_ik0
III: k = 2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
T_i10 = 0
T_i11 = -math.inf
T_i20 = 0
T_i21 = -math.inf
for price in prices:
T_i20 = max(T_i20, T_i21 + price)
T_i21 = max(T_i21, T_i10 - price)
T_i10 = max(T_i10, T_i11 + price)
T_i11 = max(T_i11, 0 - price)
return T_i20
IV: k = any
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# same as #2 where k = inf
if k >= len(prices) >> 1: # n / 2
T_ik0 = 0
T_ik1 = -math.inf
for price in prices:
T_ik0_old = T_ik0 # store prev hold/sell max T[i-1][k][0]
T_ik0 = max(T_ik0, T_ik1 + price) # hold, prev buy + sell at this price
T_ik1 = max(T_ik1, T_ik0_old - price) # hold, prev hold/sell max + buy more at this price
return T_ik0
T_ik0 = [0] * (k+1)
T_ik1 = [-math.inf] * (k+1)
for price in prices:
for j in range(k, 0, -1):
T_ik0[j] = max(T_ik0[j], T_ik1[j] + price)
T_ik1[j] = max(T_ik1[j], T_ik0[j-1] - price)
return T_ik0[k]
// cause Python will TLE
class Solution {
public int maxProfit(int k, int[] prices) {
if (k >= prices.length >>> 1) {
int T_ik0 = 0, T_ik1 = Integer.MIN_VALUE;
for (int price : prices) {
int T_ik0_old = T_ik0;
T_ik0 = Math.max(T_ik0, T_ik1 + price);
T_ik1 = Math.max(T_ik1, T_ik0_old - price);
}
return T_ik0;
}
int[] T_ik0 = new int[k + 1];
int[] T_ik1 = new int[k + 1];
Arrays.fill(T_ik1, Integer.MIN_VALUE);
for (int price : prices) {
for (int j = k; j > 0; j--) {
T_ik0[j] = Math.max(T_ik0[j], T_ik1[j] + price);
T_ik1[j] = Math.max(T_ik1[j], T_ik0[j - 1] - price);
}
}
return T_ik0[k];
}
}