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 $price{s}_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=\infty$.

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(price{s}_0,price{s}_1,...,price{s}_i)$.

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

Compute the answer $res=\underset{0\le i<n}{\max }(price{s}_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=\infty$.

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(price{s}_0,price{s}_1,...,price{s}_i)$.

  min_price = min(min_price, price)

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

  res = max(res, price - min_price)

Print the answer.

print(res)