Quick Overview

This question evaluates proficiency in dynamic programming, state modeling for sequential decision problems, and algorithmic optimization related to constrained transaction planning.

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.

Overview: 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

  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.

Loading coding console...

Show the approach

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)