578. Many Small Trades
A market trader tracks the price of one commodity over n consecutive days: prices[i] is the price on day i. The trader may buy and sell as often as they like, but can hold at most one unit at any moment, so a unit must be sold before another is bought. Selling and buying again on the same day is allowed. Each trade has no fee.
Return the largest total profit the trader can collect. If prices only fall, the best choice is not to trade at all and the answer is 0.
Because the number of days can reach one hundred thousand, an approach that compares every pair of days (O(n^2)) will time out. A single linear scan with O(1) extra memory is intended. The result always fits in a 32-bit signed integer.
Example 1
- Input:
- prices = [4,2,6,6,9,3]
- Output:
- 7
- Explanation:
Buy at 2 and sell at 9 for a profit of 7, which equals collecting the rises 2 to 6 and 6 to 9 separately.
Example 2
- Input:
- prices = [9,7,4,2]
- Output:
- 0
- Explanation:
Prices fall every day, so no trade is profitable and the answer is 0.
Example 3
- Input:
- prices = [3,8,2,5]
- Output:
- 8
- Explanation:
Buy at 3 and sell at 8 for 5, then buy at 2 and sell at 5 for 3, for a total of 8.
Constraints
1 ≤ prices.length ≤ 1000000 ≤ prices[i] ≤ 10000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)