# Best Time to Buy and Sell Stock IV

## Intuition

Any solution with i days could be separated into 2 kinds,

1. Last day is the end of the last transaction
2. Last day is not in any transaction

j: Max transactions number global local

diff = prices[i] - prices[i-1] local[i][j] = max(local[i-1][j]+diff, global[i-1][j-1] + diff) global[i][j] = max(local[i][j], global[i-1][j])

## Solution

``````
class Solution:
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if len(prices) < 2:
return 0

if k >= len(prices) / 2:
return sum(
b - a
for a, b in zip(prices[:-1], prices[1:])
if b > a
)

local_max = [0] * (k + 1)
global_max = [0] * (k + 1)

for i in range(1, len(prices)):
diff = prices[i] - prices[i-1]

for j in range(k, 0, -1):
local_max[j] = max(local_max[j], global_max[j-1]) + diff
global_max[j] = max(local_max[j], global_max[j])

return global_max[k]

def main():
cases = (
(2, [3, 2, 6, 5, 0, 3]),
(2, [1, 3, 2, 6, 5, 0, 3]),
)
for args in cases:
print(Solution().maxProfit(*args))

if __name__ == '__main__':
main()

``````