Maximize profit from one or many stock trades
Company: Squarepoint
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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`.
2. **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.
Quick Answer: 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.