Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:


Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.


Example 2:


Input: [3,2,6,5,0,3], k = 2
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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'class Solution:\n     def maxProfit(self, k, prices):\n         """\n         :type k: int\n         :type prices: List[int]\n         :rtype: int\n         """\n         \'\'\'\n         https://www.youtube.com/watch?v=oDhu5uGq_ic\n \n             i: number of transactions\n             j: jth day \n \n             Total[i][j] = max(T[i][j-1], max((price[j] - price[m]) + T[i-1][m] for m in range(0, j-1)))\n             \n             NOTEs:\n                 1. use cache\n                 2. no need to initialize a 2D array, it takes too long\n     \n         \'\'\'\n         prices_length = len(prices)\n         if prices_length == 0:\n             return 0\n         if k == 0:\n             return 0\n \n         # For N days, there will be at most N/2 transactions (N/2 buys and N/2 sells)\n         # One buy + One sell = One transaction\n         # When k is big enough to allow us buy/sell as many as we want, this becomes type-II \n         # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/\n         if 2*k > (prices_length+1):\n             profit = 0\n             max_price = prices[0]\n             min_price = prices[0]\n \n             for p in prices:\n                 if p < max_price:\n                     profit += (max_price - min_price)\n                     max_price = min_price = p\n                 else:\n                     max_price = p \n                     \n             profit += (max_price - min_price)\n     \n             return profit\n \n         # Generic solution \n         candidate_max = float(\'-inf\')\n         profit = [0] * prices_length\n         for trans in range(1, k+1):\n \n             cache = -prices[0]\n             max_profit = 0\n             for d in range(1, prices_length):\n                 if 2*trans > d+1: continue # For a given day, there are too many transaction allowed, no need to compute\n \n                 cache = -prices[d-1] + profit[d-1] if -prices[d-1] + profit[d-1] > cache else cache \n                 new_profit = prices[d] + cache \n                 \n                 # profit[d-1] has been used (the above line), now update it before \'max_profit\' gets updated\n                 profit[d-1] = max_profit\n \n                 max_profit = max_profit if max_profit > new_profit else new_profit\n \n             # When loop ends, do one last update\n             profit[-1] = max_profit\n             candidate_max = profit[-1] if profit[-1] > candidate_max else candidate_max\n \n \n         result = candidate_max if candidate_max > 0 else 0\n         return result'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'maxProfit'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5954