Given an array prices[] of non-negative integers representing a stock price on…
2025202420252024
Given an array prices[] of non-negative integers representing a stock price on each day, find the maximum profit obtainable with at most one transaction. One transaction consists of one buy followed by one sell on a later day. Return 0 when no positive profit is possible.
Note: The stock must be bought before it is sold.
Input format
The first line contains a single integer n — the number of days, that is the size of prices[].
The second line contains n space-separated integers prices[0], prices[1], …, prices[n-1].
Output format
Print a single integer — the maximum profit obtainable with at most one transaction, or 0 when no positive profit is possible.
For prices[] = [1, 3, 6, 9, 11] the standard input is:
5
1 3 6 9 11and the required standard output is:
10Examples
Input: prices[] = [7, 10, 1, 3, 6, 9, 2]
Output: 8
Explanation: Buy at index 2 for price 1 and sell at index 5 for price 9. The profit is 9 - 1 = 8.
Input: prices[] = [7, 6, 4, 3, 1]
Output: 0
Explanation: Prices decrease throughout, so no later selling price exceeds an earlier buying price.
Input: prices[] = [1, 3, 6, 9, 11]
Output: 10
Explanation: Buy at index 0 for price 1 and sell at the last index for price 11. The profit is 10.
Constraints
1 ≤ prices.size() ≤ 105
0 ≤ prices[i] ≤ 104
Attempted by 1 students.
Show answer & explanation
Concept
For one buy followed by one later sell, the profit at a selling day equals the current price minus the minimum price seen on an earlier day.
A left-to-right scan maintains two invariants: minPrice is the minimum value in the processed prefix, and maxProfit is the largest valid sell-minus-earlier-buy difference found so far.
Application
Initialize minPrice to the first array value and maxProfit to 0.
For each later price p, compute candidateProfit = p - minPrice and update maxProfit with the larger of its current value and candidateProfit.
After evaluating p, update minPrice with the smaller of minPrice and p. This order ensures that every profit uses a buying day no later than the current selling day; because the transaction must use different days, the scan begins at the second element.
For [7, 10, 1, 3, 6, 9, 2], minPrice becomes 1 at index 2. At price 9, candidateProfit is 9 - 1 = 8, which becomes the maximum.
Cross-check
For [7, 6, 4, 3, 1], every candidate profit is non-positive, so maxProfit remains 0.
For [1, 3, 6, 9, 11], minPrice remains 1 and the final candidate profit is 11 - 1 = 10.
Therefore, the required maximum profit is returned after one scan. Time complexity is O(n) and auxiliary space is O(1).