Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot short a stock (sell a stock before you buy one.)
Example 1:
Input: [8,3,7,2,8,9]
Output: 7
Explanation: Since Buying price should always be less than selling price and the difference should be maximum. We take 2 as the buying price and sell it in price of 9.
Example 2:
Input: [6,4,3,2]
Output: 0
Explanation: Buying price should less than selling price, so no transaction is done.
Solution
The first thing to note about this problem is that- to make a sell, we need to buy the stock first. If we draw this values in a simple graph, we will see that the problem is based on peaks(sell) and valleys(buy). Hence we have to choose the smallest valley first then the highest peak for the profit to become maximum.
We can define two variables, one for the minimum price and second for the maximum profit. While traversing through the array, for each scenario, we will calculate and update minimum price and maximum profit as well. For each iteration there can be only two situations:
- if
prices[i]< minimum price, then minimum price will be equal toprices[i]. - Else, maximum profit will be equal to maximum of (maximum profit,
prices[i]– minimum price).
After the iteration, return maximum profit.
Solution Implementation
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
vector<int> vec = { 8,3,7,2,8,9 };
int minPrice = INT_MAX;
int maxProfit = 0;
for(int i = 0; i < vec.size(); i++) {
if (vec[i] < minPrice) {
minPrice = vec[i];
}
else {
maxProfit = max(maxProfit, vec[i] - minPrice);
}
}
cout << "Maximum Profit = " << maxProfit << "\n";
return (0);
}
Complexity Analysis
- Time complexity: O(n).
- Space complexity: O(1).
