Best Time to Buy and Sell Stock

Given an array where the element at the index i represents the price of a stock on day i, find the maximum profit that you can gain by buying the stock once and then selling it.

Note

You can buy the stock on one specific day and sell it on a different day to make a profit. If no profit can be achieved, we return zero.

Constraints

• We can't sell before buying a stock, that is, the array index at which stock is bought will always be less than the index at which the stock is sold.
• 1 ≤ prices.length ≤ 10³
• 0 ≤ prices[i] ≤ 10⁵

Examples

Sample Example 1

Input:

• prices = [7, 1, 5, 3, 6, 4]

Output: Profit = 5

Explanation: The stock will be purchased on Day 2 and then sold on Day 5 to maximize profit.

Sample Example 2

Input:

• prices = [7, 6, 4, 3, 1]

Output: Profit = 0

Explanation: No profit can be generated with this sequence of stock prices.