19. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the stock price on day i. You may buy once and sell once (buy before sell). Return the maximum profit possible, or 0 if no profit is achievable.

Input: An integer array prices of length n.

Output: Integer — maximum profit, or 0 if none possible.

Examples

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy day 2 (price=1), sell day 5 (price=6). Profit = 6-1 = 5. Best possible.

Input: [7,6,4,3,1]
Output: 0
Explanation: Prices only decrease. No profitable trade. Return 0.

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy day 1 (price=1), sell day 5 (price=5). Profit = 4.

Constraints

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Asked by