#158EasyGreedy· Running Minimum
Single Trade Max Profit
Input format
`prices`: an array of non-negative integers, one per day.
Output format
An integer: the maximum profit from one buy followed by one sell, or 0 if every trade loses money.
Examples
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Buy on day 1 at price 1 and sell on day 4 at price 6 for a profit of 5. Buying at 7 would only lose money.
Input: prices = [7, 6, 4, 3, 1]
Output: 0
Prices only fall, so every possible trade loses money and the answer is 0.
Input: prices = [2, 4, 1]
Output: 2
Buy at 2 and sell at 4 for a profit of 2; the dip to 1 comes too late to sell at a higher price.
Constraints
- 1 <= prices.length <= 10^5
- 0 <= prices[i] <= 10^4
Study first
- #greedy
- #arrays
- #dynamic-programming