# A chronological and intuitive solution with explanation time O(k*n) space O(k)

• When k >= len(prices)//2 this problem reduces to the problem type II, so using that solution for that special case.
The thinking behind this code is to generalize the k = 2 case from the problem type III to k > 2.
The sequence of events, can be thought of in chronological order, the stock is traded as the following:

when buying, we spend money, when selling, we earn the profit, so profits are defined as
profit1 = -buy1 + sell1 (usually we write profit = sell_price - buy_price, but to illustrate the sequence I write buy first)
...
total money after sell1 = -buy1 + sell1 = profit1
total money after sell2 = -buy2 + sell2 + profit1 = profit2 + profit1
total money after sell3 = -buy3 + sell3 + profit2 + profit1 = profit3 + profit2 + profit1
...

The lowest price as we traverse through prices list will be assigned transaction 1 so the first one is unique:

``````                if i == 0:
sell[i] = max(sell[i], p - buy[i])
``````

But the rest of the transactions all follow the same pattern for k > 0, after the buy or sell, to maximize the total money currently with:

``````                else:
sell[i] = max(sell[i], p + buy[i])
``````

So, in the end, the loop with elements with k > 0 will all behave similarly, and we just need to return the money after the last sell. Here buy and sell indicate the total money after the buy or sell i-th transaction, and p is the buy or sell price. Hope this all makes perfect sense to everyone.

Another leetcoder found a more elegant solution without using the special case of the first transaction reversing k:
https://discuss.leetcode.com/topic/23888/concise-python-solution-with-detailed-explanation-o-kn-time-o-k-space
but just thought I share my solution since it made more sense in my head.

Complete code:

``````class Solution(object):
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if not prices or not k:
return 0
if k >= len(prices) // 2:
profit = 0
for i in range(len(prices) - 1):
nextP, currP = prices[i + 1], prices[i]
if nextP > currP:
profit += max(nextP - currP, 0)
return profit
sell = [0] * k
for p in prices:
for i in range(k):
if i == 0: