Solution For Best Time To Buy And Sell Stock
The Best Time to Buy and Sell Stock problem on LeetCode asks us to find the maximum profit that can be made by buying and then selling a stock with the given prices. In other words, we need to find the difference between the maximum price and the minimum price in the given array of stock prices.
We can solve this problem efficiently by iterating over the price array and keeping track of the minimum price seen so far and the maximum profit that can be made by buying at that minimum price and selling at the current price. We update the maximum profit at each iteration and return it as the final result.
Here is the step by step algorithm to solve this problem:
- Initialize the minimum price and maximum profit to the first price in the array.
- Iterate over the remaining prices in the array:
a. If the current price is less than the minimum price seen so far, update the minimum price.
b. Otherwise, calculate the profit that can be made by buying at the minimum price seen so far and selling at the current price. If this profit is greater than the maximum profit seen so far, update the maximum profit. - Return the maximum profit as the final result.
Here is the Python code implementation of the above algorithm:
“`python
def maxProfit(prices):
if len(prices) < 2:
return 0
min_price = prices[0]
max_profit = 0
for price in prices[1:]:
if price < min_price:
min_price = price
else:
max_profit = max(max_profit, price - min_price)
return max_profit
“`
In this code, we first handle the edge case where the length of the given price array is less than 2. If the input array has only one or no prices, we cannot make any profit, so we return 0.
If we have more than one price in the array, we initialize the minimum price to the first price and the maximum profit to 0. Then we iterate over the remaining prices in the array and update the minimum price and maximum profit at each iteration as described in the algorithm above.
Finally, we return the maximum profit as the result.
The time complexity of this algorithm is O(n) where n is the length of the input array, and the space complexity is O(1) since we only need to store the minimum price and maximum profit.
Step by Step Implementation For Best Time To Buy And Sell Stock
class Solution { public int maxProfit(int[] prices) { // keep track of the minimum price int minPrice = Integer.MAX_VALUE; // keep track of the maximum profit int maxProfit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { // update the minimum price minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit) { // update the maximum profit maxProfit = prices[i] - minPrice; } } return maxProfit; } }
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. def maxProfit(prices): # We need to keep track of the minimum value we've seen so far, as well as the maximum profit min_val = float('inf') max_profit = 0 for price in prices: # Update the minimum value if we've seen a new low if price < min_val: min_val = price # Update the maximum profit if we can get a better one else: profit = price - min_val if profit > max_profit: max_profit = profit return max_profit
var maxProfit = function(prices) { // keep track of the minimum price let minPrice = prices[0]; // keep track of the maximum profit let maxProfit = 0; for (let i = 1; i < prices.length; i++) { // if the current price is less than the minPrice, update the minPrice if (prices[i] < minPrice) { minPrice = prices[i]; } else if (prices[i] - minPrice > maxProfit) { // else if the current price minus the minPrice is greater than the maxProfit, update the maxProfit maxProfit = prices[i] - minPrice; } } return maxProfit; };
class Solution { public: int maxProfit(vector& 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; } };
public int MaxProfit(int[] prices) { int minprice = int.MaxValue; int maxprofit = 0; for (int i = 0; i < prices.Length; i++) { if (prices[i] < minprice) minprice = prices[i]; else if (prices[i] - minprice > maxprofit) maxprofit = prices[i] - minprice; } return maxprofit; } /* This code iterates through the array of prices, keeping track of the minimum value seen so far and the maximum profit that could be made by buying at the minimum value and selling at the current price. */