Given an array prices where prices[i] is the price of a stock on day i, return the maximum profit you can achieve from a single buy and a single sell. You must buy before you sell. Pattern focus: Contrast with DP. The greedy insight is to keep track of the minimum price seen so far and update the best profit whenever the current price is higher.
prices = stock prices by day
maximum profit from one transaction
Example 1:
Input:
prices = [7,1,5,3,6,4]
Output:
5
Explanation:
Buy at 1 and sell at 6 for a profit of 5.
Example 2:
Input:
prices = [7,6,4,3,1]
Output:
0
Explanation:
The price only decreases, so no profitable trade exists.
Example 3:
Input:
prices = [1,2]
Output:
1
Explanation:
Buy on day 1 and sell on day 2.