You receive an integer list of daily stock values, with prices[i] denoting the price on day i. You may perform no more than k transactions. A transaction requires purchasing a stock first and selling it on a later day, so buying and selling on the same day is not permitted. Create an algorithm that returns the greatest profit possible.
Input: An integer array prices with length n containing the daily prices. An integer k that limits how many transactions may be made.
Output: Return an integer equal to the largest attainable profit.
Constraints:
1 <= k <= 1000 <= prices[i] <= 1000Example:
Input: k = 2, prices = [5, 8, 3]
Output: 3
Explanation: Purchase on day 1 for 5 and sell on day 2 for 8, giving a profit of 8 - 5 = 3.
Input: k = 2, prices = [4, 1, 6, 3, 8]
Output: 10
Explanation: Buy on day 2 at 1 and sell on day 3 at 6 for a profit of 6 - 1 = 5. Next, buy on day 4 at 3 and sell on day 5 at 8 for a profit of 8 - 3 = 5.
Input:
2
5 7 3
Output: 2
Explanation: Buy on day 1 for 5 and sell on day 2 for 7, giving a profit of 7 - 5 = 2.