Best Time to Buy and Sell Stock — At Most K Transactions

Problem

Given an array prices and an integer k, find the maximum profit you can achieve with at most k buy-sell transactions. You must sell before you buy again.

Example

k = 2, prices = [3,2,6,5,0,3]
Output: 7  -- buy@2 sell@6, buy@0 sell@3

Constraints

• 1 ≤ k ≤ 100
• 1 ≤ prices.length ≤ 1000

Variants asked at Flipkart OA

• k = 1 (single transaction)
• k = infinity (unlimited transactions)
• With a cooldown period of 1 day after selling
• With a fixed transaction fee