π Problem Description:
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 sell a stock before you buy one.
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.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution Approach
We can solve that by iterating over the given array of prices once! We have to keep track of the minimum-price we have seen so far and in each day we'll check if we can maximize our profit by calculating the difference between minimum price we have seen so far and the price of the current day. Let's see an example -
A = [7, 1, 5, 3, 6]
maxProfit = 0, minPrice = MAX
In each iteration we'll do these
minPrice = min(A[i], minPrice)
maxProfit = max(maxProfit, A[i] - minPrice)
i = 0
minPrice = min(7, MAX) ::= 7
maxProfit = max(0, 7 - 7) ::= 0
i = 1
minPrice = min(1, 7) ::= 1
maxProfit = max(0, 1 - 1) ::= 0
i = 2
minPrice = min(5, 1) ::= 1
maxProfit = max(0, 5 - 1) ::= 4
i = 3
minPrice = min(3, 1) ::= 1
maxProfit = max(4, 3 - 1) ::= 4
i = 4
minPrice = min(6, 1) ::= 1
maxProfit = max(4, 6 - 1) ::= 5
return maxProfit ::= 5
Here's the code -
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxProfit = 0;
int minPrice = INT_MAX;
int size = prices.size();
for(int i=0; i<size; i++) {
int diff = prices[i] - minPrice;
minPrice = min(minPrice, prices[i]);
maxProfit = max(maxProfit, diff);
}
return maxProfit;
}
};
Complexity Analysis
Time Complexity O(n)
Linear time solution; only traversing the array
Space Complexity O(1)
Constant space
Top comments (0)