Description:
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 at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [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: [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: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
prices = [math.inf] + prices + [-math.inf]
cache = []
lag = 0
for i in range(1,len(prices)-1):
if prices[i] == prices[i+1]:
lag += 1
continue
if prices[i] <= prices[i-1-lag] and prices[i] <= prices[i+1]:
cache.append(prices[I])
if prices[i] >= prices[i-1-lag] and prices[i] >= prices[i+1]:
cache.append(prices[I])
lag = 0
# print(cache)
if not cache:
return 0
if len(cache) == 2:
return cache[1]-cache[0]
left_min = 0
left_ls = [cache[1]-cache[0]]
for i in range(2,len(cache)-2,2):
if cache[i] < cache[left_min]:
left_min = I
left_ls.append(max(cache[i+1] - cache[left_min], left_ls[-1]))
# print(left_ls)
cache2 = [-c for c in cache][::-1]
# print(cache2)
right_min = 0
right_ls = [cache2[1]-cache2[0]]
for i in range(2,len(cache2)-2,2):
if cache2[i] < cache2[right_min]:
right_min = I
right_ls.append(max(cache2[i+1] - cache2[right_min], right_ls[-1]))
right_ls = right_ls[::-1]
# print(right_ls[::-1])
return max([left_ls[i]+right_ls[i] for i in range(len(left_ls))])
Runtime: 76 ms, faster than 17.99% of Python3 online submissions for Best Time to Buy and Sell Stock III.
Memory Usage: 14.9 MB, less than 12.30% of Python3 online submissions for Best Time to Buy and Sell Stock III.
Description:
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 at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Example 1:
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Solutions:
TLE solution:
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices or k == 0:
return 0
prices = [math.inf] + prices + [-math.inf]
cache = []
lag = 0
for i in range(1,len(prices)-1):
if prices[i] == prices[i+1]:
lag += 1
continue
if prices[i] >= prices[i-1-lag] and prices[i] >= prices[i+1]:
cache.append(prices[I])
if prices[i] <= prices[i-1-lag] and prices[i] <= prices[i+1]:
cache.append(prices[I])
lag = 0
# print(cache)
if not cache:
return 0
if len(cache)//2 <= k:
return sum([cache[i+1]-cache[i] for i in range(0,len(cache),2)])
length = len(cache)//2
dp = [[0 for i in range(length)] for j in range(length)]
for i in range(length):
dp[i][i] = cache[2*i+1] - cache[2*i]
min_left = cache[2*I]
for j in range(i+1,length):
min_left = min(min_left,cache[2*j])
dp[i][j] = max(dp[i][j-1], cache[2*j+1] - min_left)
# for d in dp:
# print(d)
def helper(start,k):
if k == 0:
return 0
if k == 1:
return dp[start][-1]
cache = []
for i in range(start,length-k+1):
cache.append(dp[start][i] + helper(i+1,k-1))
return max(cache)
return helper(0,k)
Solution inspired by https://www.youtube.com/watch?v=oDhu5uGq_ic
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices or k == 0:
return 0
i = 1
prices = [math.inf] + prices + [-math.inf]
while i < len(prices)-1:
while (i < len(prices)-1) and ((prices[i-1] < prices[i] and prices[i] < prices[i+1]) or (prices[i-1] > prices[i] and prices[i] > prices[i+1]) or (prices[i] == prices[i+1])):
prices.pop(i)
else:
i += 1
prices = prices[1:len(prices)-1]
if k >= len(prices)//2:
return sum([prices[i*2+1] - prices[i*2] for i in range(len(prices)//2)])
last = [0 for i in range(len(prices))]
for trans in range(1,k+1):
curr = [0]
max_diff = last[0] - prices[0]
for day in range(1,len(prices)):
max_diff = max(max_diff,last[day]-prices[day])
curr.append(max([curr[-1],prices[day]+max_diff]))
last = curr
return last[-1]
Runtime: 96 ms, faster than 60.75% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 14.5 MB, less than 15.65% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
sample 36 ms submission: 没看懂
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
h = []
st = []
v2, p2, n = 0, 0, len(prices)
while p2 < n-1:
v2 = p2
while v2 < n-1 and prices[v2] >= prices[v2+1]:
v2 += 1
p2 = v2 + 1
while p2 < n and prices[p2] >= prices[p2-1]:
p2 += 1
while st and prices[v2] < prices[st[-1][0]]:
v1, p1 = st.pop()
h.append(prices[p1-1] - prices[v1])
while st and prices[p2-1] >= prices[st[-1][1]-1]:
v1, p1 = st.pop()
h.append(prices[p1-1] - prices[v2])
v2 = v1
st.append((v2,p2))
h = heapq.nlargest(k, h)[::-1]
# heapq.heapify(h)
while st:
v, p = st.pop()
profit = prices[p-1] - prices[v]
if len(h) < k:
heapq.heappush(h, profit)
else:
heapq.heappushpop(h, profit)
return sum(h)
