LeetCode 솔루션 분류
[9/10] 188. Best Time to Buy and Sell Stock IV
본문
Hard
5527185Add to ListShareYou are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.
Find the maximum profit you can achieve. You may complete at most k transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: k = 2, prices = [2,4,1] Output: 2 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:
Input: k = 2, prices = [3,2,6,5,0,3] 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.
Constraints:
0 <= k <= 1000 <= prices.length <= 10000 <= prices[i] <= 1000
Accepted
312,832
Submissions
839,821
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 92 ms, faster than 95.38% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 13.8 MB, less than 94.99% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
Memory Usage: 13.8 MB, less than 94.99% of Python3 online submissions for Best Time to Buy and Sell Stock IV.
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices: return 0
dp = [0]*len(prices) # profits
if k > len(prices):
res = 0
for i in range(1,len(prices)):
if prices[i] - prices[i-1] > 0 : res += prices[i] - prices[i-1]
return res
for _ in range(k):
prof_minus_price = -prices[0]
profit = 0
for i in range(1, len(dp)):
prof_minus_price = max(prof_minus_price, dp[i] - prices[i])
profit = max(profit, prof_minus_price + prices[i])
dp[i] = profit
return dp[-1]
