Bloomberg Hard Interview Questions

Background: In the financial domain, Bloomberg provides tools for stock market analysis, including trading strategies. Understanding how to maximize profit through stock trading is crucial for building robust trading systems.
Problem statement: You are given an array of integers where each integer represents the price of a stock on a given day. You can complete at most k transactions (i.e., buy and sell the stock). Your goal is to maximize your profit. You can assume that you cannot sell a stock before you buy it. You need to implement a function that calculates the maximum profit that can be achieved with at most k transactions.Function signature:

def max_profit(k: int, prices: List[int]) -> int:

Example 1:
Input: k = 2, prices = [2, 4, 1, 7, 5]
Output: 7
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 2. Buy on day 3 (price = 1) and sell on day 4 (price = 7), profit = 6. Total profit = 2 + 6 = 8. Example 2:
Input: k = 1, prices = [3, 2, 6, 5, 0, 3]
Output: 4
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6 - 2 = 4.Constraints:

• 1 <= k <= 100


• 0 <= prices.length <= 1000


• 0 <= prices[i] <= 1000