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
