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