Maximize Stock Trading Profits Using Dynamic Programming

Scenario

Evaluating dynamic-programming skills on stock-trading profits.

Question

Given an array of daily stock prices and an integer K, write Python code that returns the maximum profit obtainable with at most K buy-sell transactions.

Hints

Describe and implement a bottom-up DP running in O(K·N) time and O(N) space.

Max Profit with At Most K Transactions

Given an integer array prices where prices[i] is the price of a stock on day i and an integer k, return the maximum profit achievable using at most k buy-sell transactions. You may hold at most one share at a time and must sell before buying again. If no profit is possible, return 0.

Constraints

• 0 <= len(prices) <= 10000
• 0 <= k <= 1000
• 0 <= prices[i] <= 10^9
• At most one position at any time; buy before next sell
• Time target: O(k·n) and O(n) space; optimize to O(n) time if k >= n/2

Examples

Example 1

Input: prices = [3,2,6,5,0,3], k = 2
Output: 7

Explanation: Buy at 2, sell at 6 (profit 4); buy at 0, sell at 3 (profit 3). Total = 7.

Example 2

Input: prices = [5,4,3,2,1], k = 3
Output: 0

Explanation: Prices decrease every day; no profitable transaction.

Hints

1. If k >= n/2, it is equivalent to unlimited transactions; sum all positive price differences.
2. Use DP: for each t in [1..k], compute cur[i] = max(cur[i-1], prices[i] + best) where best = max(best, prev[i] - prices[i]).
3. Roll arrays (prev, cur) to keep O(n) space.

Approach

Handle the unlimited-transactions shortcut when k >= n/2 by summing all positive day-to-day price increases. Otherwise, use a bottom-up DP: let prev[i] be the max profit up to day i with at most t-1 transactions, and cur[i] be the max profit with at most t transactions. For each t, maintain best = max(prev[j] - prices[j]) for j < i. Then cur[i] = max(cur[i-1], prices[i] + best). Rolling arrays reduce space to O(n).

• Time complexity: O(k·n)
• Space complexity: O(n)