This DP solution is well explained on: https://discuss.leetcode.com/topic/4766/a-clean-dp-solution-which-generalizes-to-k-transactions/2.
Although I used O(n) space (we only need to keep track of two n-length arrays in each iteration) with O(nk) time complexity, I still got TLE in one of the tests where k >= len(prices)/2. In this case, the problem is conveniently reduced to stock II. So I reused the function I wrote for that to handle the egde case:
class Solution(object): def maxProfit(self, k, prices): if not k or not prices: return 0 l = len(prices) if k >= l/2: return self.stock2(prices) f = [[0 for _ in range(l)],[0 for _ in range(l)]] for i in range(1, k+1): tmpmax = - prices for j in range(1, l): f[j] = max(f[j-1], prices[j] + tmpmax) tmpmax = max(tmpmax, f[j] - prices[j]) f, f = f, [0 for _ in range(l)] return f[-1] def stock2(self, prices): maxprof = 0 for i, p in enumerate(prices): if i != 0 and prices[i] - prices[i-1] > 0: maxprof += prices[i] - prices[i-1] return maxprof
Nice solution. Just refine the code a little bit.
def maxProfit(k, prices): n = len(prices) if k > n/2: # if k is too large, all potential profit can be earned return sum([prices[i] - prices[i-1] for i in range(1, n) \ if prices[i] > prices[i-1] ]) f, fnew =  * n,  * n # ping-pong dp, maximum profit can get then for _ in range(k): tmax = - prices # the money I have today for i in range(1, n): fnew[i] = max(fnew[i-1], prices[i] + tmax) # do nothing or sell one tmax = max(tmax, f[i] - prices[i]) # max money after this day f, fnew = fnew,  * n return f[n-1] '''