Best Time to Buy and Sell Stock
DESCRIPTION (credit Leetcode.com)
Write a function to determine the maximum profit you can obtain from a series of stock prices given in an array prices, where prices[i] represents the stock price on the ith day. You are allowed to buy and then sell the stock once, as long as as the sell date is after the buy date. If no profit can be made, the function should return 0.
EXAMPLES
Input:
prices = [3,4,6,2,5,8]
Output:
6
Explanation: Buy on day 4 (price = 2) and sell on day 6 (price = 8), profit = 8-2 = 6.
Input:
prices = [9,7,5,3,1]
Output:
0
Explanation: Prices are in descending order, so there's no opportunity to make a profit, thus the maximum profit = 0.
Solution
def maxProfit(prices):if not prices:return 0min_price = prices[0]max_profit = 0for price in prices:min_price = min(min_price, price)max_profit = max(max_profit, price - min_price)return max_profit
Explanation
The problem is asking for the maximum profit that can be made by buying and selling a stock. The key to solving this problem is to find the minimum price to buy and the maximum price to sell.
We can solve this problem by using a greedy approach. We iterate through the array, and at each day, we'll see how much profit we can make by greedily selling the stock at that day. At the end of the iteration, the maximum of those profits will be the maximum profit we can make.
To help us calculate the maximum profit, we need two variables: min_price, which represents the minimum price we have seen so far, and max_profit, which represents the maximum profit we can make so far. At each day, we can calculate the max profit on each day by subtracting the minimum price from the current price. If that leads to a profit greater than the maximum profit we have found so far, we can update max_profit.
def maxProfit(prices):if not prices:return 0min_price = prices[0]max_profit = 0for price in prices:min_price = min(min_price, price)max_profit = max(max_profit, price - min_price)return max_profit
Complexity Analysis
- Time complexity: O(n). We only iterate through the array once.
- Space complexity: O(1)
Loading comments...