Best Time to Buy and Sell Stock leetcode solution
The "Best Time to Buy and Sell Stock" problem on LeetCode can be solved using a simple approach based on finding the minimum price and the maximum profit.
The problem statement asks us to find the maximum profit that can be obtained by buying and selling a stock on consecutive days. The input is an array of prices, where each element represents the price of the stock on a particular day.
To solve this problem, we can iterate through the array of prices and keep track of the minimum price we have seen so far and the maximum profit we can obtain. We start with an initial minimum price of the first element and an initial maximum profit of 0.
Here is the step-by-step explanation of the solution:
- Initialize two variables:
minPrice
andmaxProfit
to keep track of the minimum price and maximum profit, respectively. - Iterate through the array of prices from the second element (index 1) to the end.
- At each iteration, check if the current price is less than the minimum price. If it is, update the minimum price to the current price.
- Otherwise, calculate the profit by subtracting the minimum price from the current price. If the calculated profit is greater than the maximum profit, update the maximum profit.
- After the iteration, return the maximum profit.
The time complexity of this solution is O(n), where n is the length of the input array, since weBest Time to Buy and Sell Stock Leetcode Solution in C++
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
};
Explanation:
- Declare variables
minPrice
andmaxProfit
and initializeminPrice
toINT_MAX
andmaxProfit
to0
. - Iterate through the
prices
array using a for loop. - If the current price is less than
minPrice
, updateminPrice
to the current price. - If the difference between the current price and
minPrice
is greater thanmaxProfit
, updatemaxProfit
to this difference. - Return the final
maxProfit
value.