Implement drawdown, single-trade profit, coin change

Implement and analyze the following three problems:

1. Maximum drawdown of cumulative PnL: "What is the maximum drawdown of a cumulative PnL (profit and loss) series, and when did it occur?" Write mdd(pnl) that returns: (a) the maximum drawdown as a negative number; (b) the start index (just after the peak before the drawdown starts); and (c) the end index (where the maximum drawdown ends). State time and space complexity.
2. Single-trade stock profit (LeetCode-inspired): Given an integer array prices where prices[i] is the price on day i, compute the largest profit achievable by buying once and selling on a later day. If no profitable trade exists, return 0. Design an O(n) time, O(1) space solution and explain the intuition.
3. Minimum coins for target amount (LeetCode-inspired): Given coin denominations coins and a target amount, return the smallest number of coins needed to reach the target, or -1 if it cannot be formed. Assume unlimited coins of each type. Provide a dynamic programming approach and analyze time and space.

Maximum Drawdown of a Cumulative PnL Series

You are given an array pnl where pnl[i] is the cumulative profit-and-loss of a trading strategy at time step i. The drawdown at any point is the drop from the running maximum (peak) seen so far down to the current value. The maximum drawdown is the largest such drop over the whole series.

Implement mdd(pnl) that returns a tuple (max_drawdown, start_index, end_index) where:

• max_drawdown is the maximum drawdown expressed as a negative number (the value at the trough minus the value at the preceding peak). If the series never declines below its running peak, the drawdown is 0.
• start_index is the index of the peak that immediately precedes the worst drawdown.
• end_index is the index of the trough where the worst drawdown is realized.

For an empty input, return (0, -1, -1). State the time and space complexity.

Example: pnl = [0, 5, 3, 8, 2, 6, 1]. The running peak reaches 8 at index 3, and the series falls to 1 at index 6, giving a drawdown of 1 - 8 = -7. Answer: (-7, 3, 6).

Constraints

• 0 <= len(pnl) <= 10^5
• -10^9 <= pnl[i] <= 10^9
• Drawdown is measured relative to the running maximum (peak) seen so far.
• If the series never falls below its running peak, the drawdown is 0.

Hints

1. Sweep once from left to right, tracking the highest cumulative PnL (and its index) seen so far.
2. At each step the current drawdown is value - runningPeak; remember the peak's index so you can report where the drop began.
3. Keep the most negative drawdown observed along with the peak index that produced it and the current index as the trough.

Best Time to Buy and Sell Stock (Single Trade)

You are given an integer array prices where prices[i] is the price of a given stock on day i. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Design an O(n) time, O(1) space solution.

Example: prices = [7, 1, 5, 3, 6, 4]. Buy on day 1 (price 1) and sell on day 4 (price 6) for a profit of 6 - 1 = 5.

Constraints

• 0 <= len(prices) <= 10^5
• 0 <= prices[i] <= 10^4
• You must buy before you sell (buy day strictly before sell day).
• Only a single buy/sell transaction is allowed.

Hints

1. As you scan left to right, track the lowest price seen so far — that is the best day to have bought before today.
2. At each day, the best profit if you sold today is price - minSoFar; keep the maximum across all days.
3. If prices only ever fall, the running best profit stays 0, which is the correct answer.

Coin Change (Minimum Coins)

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Provide a dynamic-programming approach and analyze its time and space complexity.

Example: coins = [1, 2, 5], amount = 11. The answer is 3 because 11 = 5 + 5 + 1.

Constraints

• 1 <= len(coins) <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4
• Unlimited supply of each coin denomination.

Hints

1. Let dp[a] = the minimum number of coins to form amount a; dp[0] = 0.
2. For each amount a, try every coin c <= a and relax dp[a] = min(dp[a], dp[a - c] + 1).
3. Initialize unreachable amounts to a sentinel (e.g. amount + 1); if dp[amount] is still the sentinel at the end, return -1.