Best Time to Buy and Sell Stock
Given an array prices where prices[i] is the price of a given stock on the i-th day, find the maximum profit you can achieve by buying on one day and selling on a later day.
If no profit is possible, return 0.
Example:
7,1,5,3,6,4
5
- We start by initializing the minimum price and maximum profit: min_price=7, max_profit=0.
- We then iterate through the array, updating min_price and max_profit as we find lower prices and higher profits:
- On the second day, min_price=1.
- On the third day, max_profit=5−1=4.
- On the fifth day, max_profit=6−1=5.
- The final output is max_profit=5.
Constraints:
- 1 <= len(prices) <= 10^5
- 0 <= prices[i] <= 10^4
Background Knowledge
The "Best Time to Buy and Sell Stock" problem is a classic example of a sliding window problem, although it can also be approached with a single pass through the data, keeping track of the minimum price seen so far and the maximum profit that can be achieved. The key concept here is to understand that we are looking for a subarray (or a window) within the given array of prices where the difference between the maximum and minimum values represents the maximum possible profit. This problem involves understanding how to efficiently scan through the array to find this optimal window.
In the context of dynamic programming and greedy algorithms, this problem can be solved by maintaining a running minimum of the stock prices seen so far and calculating the potential profit at each step. The idea is to buy at the lowest price and sell at the highest price, but since we can only sell after we buy, we need to ensure that our selling price is indeed after our buying price in the timeline. This problem does not require the use of a traditional sliding window of fixed size but rather a conceptual window that represents the period between buying and selling.
The mathematical concept behind this problem involves finding the maximum value of the difference between two elements in an array, with the constraint that the element representing the selling price must come after the element representing the buying price. This can be expressed as finding the maximum value of prices[j]−prices[i] where j>i. The goal is to maximize this difference, which represents the profit.
Algorithm/Approach
The general approach to solving this type of problem involves iterating through the array of prices and at each step, considering whether the current price could be a potential buying or selling point that maximizes profit. This can be achieved through a greedy algorithm that keeps track of the minimum price seen so far and the maximum profit that can be achieved up to the current point.
Step-by-Step Strategy
- Initialize variables to keep track of the minimum price seen so far and the maximum profit achievable.
- Iterate through the array of prices. For each price:
- Update the minimum price if the current price is lower.
- Calculate the potential profit if we were to sell at the current price after buying at the minimum price seen so far.
- Update the maximum profit if the calculated potential profit is higher.
- After iterating through all prices, the maximum profit variable will hold the maximum achievable profit.
Common Pitfalls
- Forgetting to update the minimum price when encountering a lower price.
- Incorrectly calculating the potential profit by not considering the constraint that selling must occur after buying.
- Not initializing variables properly before starting the iteration.
Time & Space Complexity
- Time Complexity: O(n), where n is the number of days (i.e., the length of the prices array), because we are making a single pass through the array.
- Space Complexity: O(1), because we are using a constant amount of space to store the minimum price and the maximum profit, regardless of the size of the input array.