**Problem**

You are given an array `prices`

where `prices[i]`

is the price of a given stock on the `i`

day.^{th}

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:5Explanation: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()): 3. If prices[i] < prices[minBuyPrice]: 4. minBuyPrice = i 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) {
int profit=0, maxProfit=0, buy=0;
for (int i=0; i<prices.size(); i++) {
if (prices[i] < prices[buy]) {
buy = i;
}
profit = prices[i] - prices[buy];
if (profit > maxProfit) {
maxProfit = profit;
}
}
return maxProfit;
}
};
```

**Output**

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