Arrays and Hashing One pass with running state
70. Best Time to Buy and Sell Stock
You are given an array prices, where prices[i] is the price of one share on day i. You may buy one
share on one day and sell it on a later day. Return the largest profit that one such trade can make.
The profit of a trade is the selling price minus the buying price. If every possible trade loses money or breaks even, do not trade, and return 0.
Example 1
Input: prices = [7, 3, 8, 2, 6, 9, 4]
7Explanation: Buy on day 3 at 2 and sell on day 5 at 9, for a profit of 7. Buying at 3 on day 1 and selling at 9 makes only 6.
Example 2
Input: prices = [9, 7, 4, 1]
0Explanation: The price falls every day, so every trade loses money. Not trading gives 0.
Example 3
Input: prices = [5, 12, 1, 3]
7Explanation: The lowest price, 1, comes after the highest, 12, so no trade can buy at 1 and sell at 12. The best trade buys at 5 on day 0 and sells at 12 on day 1.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ prices.length ≤ 1050 ≤ prices[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.