Optimum Time to Buy and Sell Stock for maximum profit explanation with solution in C++

Example 1:

Input: [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.
Not 7-1 = 6, as selling price needs to be larger than buying price.

The solution for this problem is straight forward.

We take 2 variables i.e minPrice and maxProfit. minPrice will have the minimum price from day 0 to I, and maxProfit will have maxProfit from day 0 to i.

The calculation will be, from the day 1, calculate the minPrice with below equation:

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

For maxProfit use the below equation:

        maxProfit = max(maxProfit, prices[i] - minPrice);

Finally return the maxProfit.

Solution in C++:

#include<iostream>
#include<vector>
using namespace std;

int get_max_profit(vector<int> &prices) 
{
	int maxProfit = 0;
	int minPrice = INT_MAX;
	for(int i = 0; i < prices.size(); i++)
	{
	    minPrice = min(minPrice, prices[i]);
	    maxProfit = max(maxProfit, prices[i] - minPrice);
	}
	return maxProfit;
}

int main()
{	
	vector<int> prices; 
    prices.push_back(7);
    prices.push_back(1);
    prices.push_back(5);
    prices.push_back(3);
    prices.push_back(6);
    prices.push_back(4);

    cout<<"The maximum profit is " << get_max_profit(prices)<<endl;
	return 0;
}

Output:

The maximum profit is 5

List Of Tutorials available in this website: