11427. Best time to buy and sell stock

You are given an array of prices, where prices_i contains the price of a stock on the i-th day.

You want to maximize your profit by selecting one day to buy one stock and choosing another day in the future to sell that stock.

Find the maximum profit that can be obtained from this transaction.

Input. The first line contains the size n (n ≤ 10⁵) of the price array. The second line contains the array of prices – n integers, each not exceeding 10⁴.

Output. Print the maximum profit that can be obtained from one transaction. If it is impossible to obtain profit, print 0.

Sample input 1	Sample output 1
8 6 3 6 4 2 4 8 3	6

Sample input 2	Sample output 2
4 5 5 3 2	0

SOLUTION

greedy

Algorithm analysis

We will maintain the minimum price value on the prefix of the input array. Let on the i-th iteration min_price = min(prices₀, prices₁, …, prices_i).

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₀, prices₁, …, prices_i).

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

Compute the answer res =

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₀, prices₁, …, prices_i).