Greedy Algorithms
Best Time to Buy and Sell Stock
DESCRIPTION (inspired by 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.
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
best time to buy and sell stock
0 / 7
Explanation
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
price = 5
0 / 1
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the array. We only iterate through the array once.
Space Complexity: O(1) We only use constant extra space for variables.
Your account is free and you can post anonymously if you choose.