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
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.