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:

• Day 1: price = 100$, curr_min = 100$, curr_maxprofit = 0$.
• Day 2: price = 5$, curr_min = 5$, curr_maxprofit = 0$.
• Day 3: price = 7$, curr_min = 5$, curr_maxprofit = 2$.
• Day 4: price = 34$, curr_min = 5$, curr_maxprofit = 29$.
• Day 1: price = 100$, curr_min = 5$, curr_maxprofit = 95$.
• Day 1: price = 2$, curr_min = 2$, curr_maxprofit = 95$.

The function returns 95.

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;
	}