prices[i] is the price of one share on day i. You may make one trade: buy on one day, then sell on a later day. Return the largest profit such a trade can make.
If every possible trade would lose money, do not trade, and return 0.
Example 1
Input
prices = [9, 4, 8, 2, 10, 6]
Output
8
Explanation
buy at 2 (prices[3]) and sell at 10 (prices[4]) for a profit of 8. Buying at 4 and selling at 10 would make only 6.
Example 2
Input
prices = [8, 6, 5, 3]
Output
0
Explanation
the price only falls, so every trade loses money and the best choice is not to trade.
Example 3
Input
prices = [2, 4, 1]
Output
2
Explanation
the lowest price, 1, comes on the last day, so there is no later day to sell. Buy at 2 and sell at 4.
Constraints:
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.