엔지니어 게시판
LeetCode 솔루션 분류

[9/10] 188. Best Time to Buy and Sell Stock IV

컨텐츠 정보

본문

Hard
5527185Add to ListShare

You 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 <= 100
  • 0 <= prices.length <= 1000
  • 0 <= 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.
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]
전체 404 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 767 명
  • 오늘 방문자 5,079 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0