72 ms Python code O(KN) time O(N + K) space 100%


  • 1
    R

    import sys

    class Solution(object):

    def maxProfit(self, k, prices):
        if not k or not prices:
            return 0
        simple_prices = []
        ascend = False
        total = len(prices)
        for n in range(1, total):
            if prices[n] - prices[n - 1] > 0 and not ascend:
                ascend = True
                simple_prices.append(prices[n - 1])
            if prices[n] - prices[n - 1] < 0 and ascend:
                ascend = False
                simple_prices.append(prices[n - 1])
        if ascend:
            simple_prices.append(prices[total -1])
        total = len(simple_prices)
        if k >= total/2:
            profit = 0
            for n in range(total - 1):
                diff = simple_prices[n + 1] - simple_prices[n]
                if diff > 0:
                    profit += diff
            return profit
        
        buys = [-sys.maxint]*k
        sells = [0]*k
        for price in simple_prices:
            profit = 0
            for i in range(k):
                outcome = profit - price
                if outcome > buys[i]: buys[i] = outcome
                outcome = buys[i] + price
                if outcome > sells[i]: sells[i] = outcome
                profit = sells[i]
        return sells[k-1]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.