Maximize Stock Trading Profits Using Dynamic Programming
Company: Citadel
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### 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.
Quick Answer: This question evaluates proficiency in dynamic programming, state modeling for sequential decision problems, and algorithmic optimization related to constrained transaction planning.
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
Solution
from typing import List
def max_profit_k_transactions(prices: List[int], k: int) -> int:
n = len(prices)
if k <= 0 or n < 2:
return 0
# If k is large, this becomes the unlimited transactions case.
if k >= n // 2:
profit = 0
for i in range(1, n):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit
# DP with O(k*n) time and O(n) space.
prev = [0] * n # dp for t-1 transactions
for t in range(1, k + 1):
cur = [0] * n
best = -prices[0] # best value of prev[j] - prices[j] for j < i
for i in range(1, n):
cur[i] = max(cur[i - 1], prices[i] + best)
best = max(best, prev[i] - prices[i])
prev = cur
return prev[-1]
Explanation
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).
Hints
- If k >= n/2, it is equivalent to unlimited transactions; sum all positive price differences.
- 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]).
- Roll arrays (prev, cur) to keep O(n) space.