Katkat
Back

Maximize profit from one or many stock trades

SquarepointData Scientist · Technical Screen
HardData ScientistTechnical ScreenCoding & Algorithms

Last updated

This question evaluates algorithmic problem-solving skills, particularly efficient array processing and profit-optimization across single-transaction and multiple-transaction variants, along with time and space complexity analysis.

You are given an integer array prices where prices[i] is the price of a stock on day i (0-indexed).

Answer the following two subproblems:

  1. Single transaction
  • You may complete at most one transaction: choose one day to buy and a later day to sell (must buy before you sell).
  • You are not allowed to short-sell.
  • Return the maximum profit you can achieve. If you cannot make any profit, return 0.
  1. Multiple transactions
  • You may complete as many transactions as you like (i.e., buy and sell multiple times), but you cannot hold more than one share at a time (you must sell the stock before you buy again).
  • You are not allowed to short-sell.
  • Return the maximum total profit you can achieve.

Assume:

  • 1 <= n <= 10^5, where n is the length of prices.
  • 0 <= prices[i] <= 10^4.

Design efficient algorithms for both subproblems and analyze their time and space complexity.