# Best Time to Buy and Sell Stock [Interview Question]

Problem
You are given an array prices where prices[i] is the price of a given stock on the ith day.

You need to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5

Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
###### Best time to buy and sell stock solution

Approach

In this approach, we will find the largest number followed by the smallest number. We can maintain two variables – minBuyPrice and maxProfit corresponding to the smallest number and maximum profit (maximum difference between selling price and min-price) obtained so far respectively.

Pseudocode

1. minBuyPrice = 0, maxProfit = 0, setting minBuyPrice index to the starting of the array and maxProfit to zero.
2. Traverse the array prices (0 <= i < prices.size()):
5.   profit = prices[i] - prices[minBuyPrice]
6.   if (profit > maxProfit):
7.     maxProfit = profit
8.   return maxProfit

Time Complexity: O(n), where n is the size of prices array
Space complexity : O(1)

Code Implementation

class Solution {
public:

int maxProfit(vector<int>& prices) {

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

if (profit > maxProfit) {
maxProfit = profit;
}
}

return maxProfit;
}
};


Output

Your input
[7,1,5,3,6,4]
Output
5
Expected
5