Best Time to Buy and Sell Stock (Editorial)

We will maintain the minimum price value on the prefix of the input array. Let on the $i$-th iteration

Then if we sell the stock on the $i$-th iteration, the profit will be prices_i - min\_price.

Among all such differences, find the largest one. So, the answer is

Example

Consider the first example.

To obtain the maximum profit, one should buy the stock for $2$ and sell it for $8$. Thus, the profit will be 8 - 2 = 6.

Algorithm realization

Read the input data.

scanf("%d", &n);
prices.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &prices[i]);

Initialize min\_price = ∞.

min_price = INT_MAX;

Compute the maximum profit in the variable $res$.

res = 0;

Iterate through the stock prices.

for (i = 0; i < prices.size(); i++)
{

On the $i$-th iteration min\_price = min(prices_0, prices_1, ..., prices_i).

   min_price = min(min_price, prices[i]);

Compute the answer res = \underset{0 \le i < n}{max}(prices_i - min\_price)

   res = max(res, prices[i] - min_price);
}

Print the answer.

printf("%d\n", res);

Python realization

import sys

Read the input data.

n = int(input())
prices = list(map(int, input().split()))

Initialize min\_price = ∞.

min_price = sys.maxsize

Compute the maximum profit in the variable $res$.

res = 0

Iterate through the stock prices.

for price in prices:

On the $i$-th iteration min\_price = min(prices_0, prices_1, ..., prices_i).

  min_price = min(min_price, price)

Compute the answer res = \underset{0 \le i < n}{max}(prices_i - min\_price)

  res = max(res, price - min_price)

Print the answer.

print(res)