BL
U

43. Best Time to Buy and Sell Stock

Med.

Problem Description

Given an array of NN integers representing daily stock prices, find the maximum profit obtainable from completing at most one transaction (one buy and one sell, with sell occurring after buy). If no profit can be made, output 0.

Input Format

  • •Line 1: An integer NN (1≤N≤1051 \le N \le 10^5).
  • •Line 2: NN space-separated integers P1,…,PNP_1, \dots, P_N.

Output Format

Print the maximum profit.

Example 1:
Input:
6
7 1 5 3 6 4
Output:
5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.
Example 2:
Input:
5
7 6 4 3 1
Output:
0
Explanation: Prices decrease monotonically; maximum profit is 0.
Example 3:
Input:
2
2 4
Output:
2
Explanation: Buy at 2, sell at 4, profit = 2.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online