Do you feel like trading today ?
Imagine you are in a bank as a trader and your boss wants you to make the bank earn
a lot of money. You are given an array of stock prices. The i^{th} element
of the array corresponds to the price of a share of the stock on day i.
You are allowed to do at most one transaction, i.e buy a share of a stock and sell it after.
The objective is to find a solution of time complexity O(n) and memory complexity O(1) that
returns the maximum profit.

For example, let [100 5 7 34 100 2] be the prices in dollars of the stock for 6 days. If I buy a share
of the stock on day 2 and I sell it on day 5, I realize the maximum profit of 95$. The function must
return 95.

Do you understand the problem ? Perfect then try to find the solution and come back in a while ;)

Reasonning step

You find it already ! Ok let compare with mine.
The time complexity has to be linear which means that we are contrained to explore all the
prices once.
Obviously, we will first buy and then we sell. That means that we will first look for a low price
and then sell it when the price is higher (we expect a lot higher).
We do not buy the share automatically on the day where the price is the lowest and we do not
sell the share when the price is the highest.
Indeed if we consider the following prices [150 5 7 34 100 2], the lowest price occurs the last day and the highest price the first
day. However, the best strategy consists of buying on day 2 when the share is 5$ and selling on day 5 when it is 100$. Both prices
are not extrema !

The idea is to keep two variables: the current lowest price of the visited days and the current maximum profit.
Indeed, let consider we have a current minimum price curr_min and a current maximum profit curr_maxprofit. When
analysing the price of the next day, we can have several options. If the new price is lower than our current
lowest price then this new price becomes the current lowest price and we go directly to the next day. Else, we calculate
the profit which is the difference between the new price and the current lowest price. If this new profit is higher than
our current maximum profit then this new profit becomes the current maximum profit and we go to the next day.
Here are the steps with our previous example:

Let check if the solution fulfills the requirements. We visit all the prices just once.
The solution has therefore a time complexity of O(n) where n is the number of prices in the array.
We just use two temporary variables in addition to the array of prices. The solution has therefore a constant memory
complexity.
Ok we got it ! Our boss will be happy ;)

As usual, you can find here the source code of the solution:

int maxProfit(vector<int> &prices) {
if (prices.size() < 2)
return 0;
int min = prices[0];
int profit = 0;
for(int i = 1; i<prices.size(); i++)
{
if(prices[i] < min)
min = prices[i];
else
{
if(prices[i] - min > profit)
profit = prices[i] - min;
}
}
return profit;
}