Prompt
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want 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.
Examples
- Example 1:
- Input: prices = [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.
- Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
- Example 2:
- Input: prices = [7,6,4,3,1]
- Output: 0
- Explanation: In this case, no transactions are done and the max profit = 0.
Solutions
Right Max Scan Solution
In C++
int maxProfit(vector<int>& prices) {
vector<int> scanr(prices.size());
std::inclusive_scan(prices.rbegin(), prices.rend(),
scanr.rbegin(),
ranges::max
);
int maxi = 0;
for (int i = 0; i < prices.size(); ++i) {
maxi = max(scanr[i] - prices[i], maxi);
}
return maxi;
}Explanation
Similar to 42. Trapping Rain Water’s Array Solution, you can to a right max scan in order to get the maximum element to the right of every element. Then simply just calculate the max of the difference between the input array and the array we calculated.
Big O Analysis
Time Complexity
Auxiliary Space Complexity
One Pass Solution
In C++
int maxProfit(vector<int>& prices) {
int min_price = prices[0];
int max_profit = 0;
for (int price : prices) {
min_price = min(price, min_price);
max_profit = max(price - min_price, max_profit);
}
return max_profit;
}Explanation
We circumvent needed to do the right scan because all we have to do is calculate the profit if we sell today if we had bought at the minimum price before today. We store the max profit as we go.
Big O Analysis
Time Complexity