Introduction
Investing in the stock market can be a lucrative way to grow your wealth. However, it can also be a risky venture, as the value of stocks can fluctuate wildly from day to day. As an investor, it's important to know when to buy and sell stocks in order to maximize your profits.
The Best Time to Buy and Sell Stock problem is a classic programming problem that addresses this issue. Given an array of stock prices, the problem is to find the maximum profit that can be earned by buying and selling the stock at most once. In this blog post, we'll explore how Kadane's algorithm can be used to solve this problem efficiently.
Problem Statement
The problem can be stated as follows: given an array `prices` representing the daily prices of a stock, find the maximum profit that can be earned by buying and selling the stock at most once.
For example, consider the following array of stock prices:
[7, 1, 5, 3, 6, 4]
The maximum profit that can be earned by buying and selling the stock is 5, which corresponds to buying the stock on day 2 (when the price is 1) and selling it on day 5 (when the price is 6).
Kadane's Algorithm
Kadane's algorithm can be used to solve the Best Time to Buy and Sell Stock problem in linear time complexity. The key idea is to treat the problem as finding the maximum sum subarray of the differences between consecutive prices.
Let `diff[i]` be the difference between the prices on day `i` and `i-1`. Then the problem is equivalent to finding the maximum sum subarray of the `diff` array.
Kadane's algorithm can be used to find the maximum sum subarray of the `diff` array in linear time complexity. The maximum sum subarray corresponds to the days when the stock should be bought and sold to maximize the profit.
Algorithm in pseudocode
Here's the algorithm in pseudocode:
max_profit = 0
curr_profit = 0
for i = 1 to n-1
diff = prices[i] - prices[i-1]
curr_profit = max(curr_profit + diff, 0)
max_profit = max(max_profit, curr_profit)
return max_profit
In this algorithm, `prices` is the input array of stock prices, `n` is the length of the array, `max_profit` is the maximum profit that can be earned by buying and selling the stock, `curr_profit` is the maximum profit that can be earned by buying the stock on a previous day and selling it on the current day, and `max` is a function that returns the maximum of two integers.
Algorithm working
The algorithm works as follows:
1. We initialize `max_profit` and `curr_profit` to 0.
2. We iterate over the `prices` array, starting from the second day (`i=1`). For each day, we compute the difference `diff` between the prices on the current day and the previous day.
3. We update `curr_profit` to be the maximum of `curr_profit + diff` and 0. This ensures that `curr_profit` always represents the maximum profit that can be earned by buying the stock on a previous day and selling it on the current day.
4. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`. This ensures that `max_profit` always represents the maximum profit that can be earned by buying and selling the stock at most once.
5. We return `max_profit` as the result.
Complexity Analysis
Kadane's algorithm has a time complexity of O(n), where n is the length of the input array. This is because we only need to iterate over the input array once to compute the maximum profit that can be earned by buying and selling the stock at most once.
The space complexity of the algorithm is O(1), because we only need to use a constant amount of extra space to store the max_profit and curr_profit variables.
Example
Let's walk through an example of using Kadane's algorithm to find the maximum profit that can be earned by buying and selling the stock in the following array of stock prices:
[7, 1, 5, 3, 6, 4]
1. We initialize `max_profit` and `curr_profit` to 0.
2. We start iterating over the `prices` array. On the second day (`i=1`), the price is 1, which is lower than the price on the previous day (7). So we set `diff` to -6. We update `curr_profit` to be the maximum of `curr_profit + diff` and 0, which is -6. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`, which is 0.
3. We continue iterating over the `prices` array. On the third day (`i=2`), the price is 5, which is higher than the price on the previous day (1). So we set `diff` to 4. We update `curr_profit` to be the maximum of `curr_profit +diff` and 0, which is 4. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`, which is 4.
4. We continue iterating over the `prices` array. On the fourth day (`i=3`), the price is 3, which is lower than the price on the previous day (5). So we set `diff` to -2. We update `curr_profit` to be the maximum of `curr_profit + diff` and 0, which is 2. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`, which is still 4.
5. We continue iterating over the `prices` array. On the fifth day (`i=4`), the price is 6, which is higher than the price on the previous day (3). So we set `diff` to 3. We update `curr_profit` to be the maximum of `curr_profit + diff` and 0, which is 5. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`, which is now 5.
6. We continue iterating over the `prices` array. On the sixth day (`i=5`), the price is 4, which is lower than the price on the previous day (6). So we set `diff` to -2. We update `curr_profit` to be the maximum of `curr_profit + diff` and 0, which is 3. We update `max_profit` to be the maximum of `max_profit` and `curr_profit`, which is still 5.
7. We have now iterated over the entire `prices` array. The maximum profit that can be earned by buying and selling the stock at most once is 5, which corresponds to buying the stock on day 2 (when the price is 1) and selling it on day 5 (when the price is 6).
Solution Code:
Hands-on solution:
Leetcode solution:
zaza
Conclusion
In this blog post, we have explored the Best Time to Buy and Sell Stock problem and how Kadane's algorithm can be used to solve it efficiently. Kadane's algorithm is a simple yet powerful algorithm that can be used to find the maximum sum subarray of an array in linear time complexity.
As an investor, knowing when to buy and sell stocks can be crucial to maximizing your profits. The Best Time to Buy and Sell Stock problem provides a simple way to model this decision, and Kadane's algorithm provides an efficient way to solve it.