The link to the problem: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Say you have an array prices for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Constraint: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Input: [7,1,5,3,6,4]
Output: 7
Since we can buy on day 2 and sell on day 3; and buy on day 4 and sell on day 5.Thoughts:
This problem is the transformation of 121. Best Time to Buy and Sell Stock.
In 121, we can only make at most 1 transaction. That is to say, we can simply just keep tracking the minimum prize before position i and finding the maximum profit (i.e., the difference between prices[i] and the minimum price).
Below will be the code that solves problem 121:
public int maxProfit(int[] prices) {
if(prices==null||prices.length<=1)
return 0;
int min = prices[0];
int maxDiff = 0; //find the maxDiff
for(int i=1;i<prices.length;i++)
{
maxDiff = Math.max(prices[i]-min,maxDiff);
if(prices[i]<min)
min = prices[i];
}
return maxDiff;
}In 122, we can make as many transactions as we want. The easiest way to solve this problem is to keep adding profit once we found the profit is positive.
public int maxProfit(int[] prices) {
int profit = 0;
for(int i=1;i<prices.length;i++)
{
if(prices[i]>prices[i-1])
profit += prices[i]-prices[i-1];
}
return profit;
}⚠️The code logic seems like it is possible that we buy and sell on the same day. However, it’s just us “calculating the difference”, not really doing the sell and buy every time when we add on the differences.
For example, if the prices=[1,2,3,4,5,3,2,8].
🚧 In the code we do like: 🚧
🔧1'. buy on day 1 and sell on day 2
🔧2'. buy on day 2 and sell on day 3
🔧3'. buy on day 3 and sell on day 4
🔧4'. buy on day 4 and sell on day 5
🔧5'. buy on day 5 and found that we cannot sell on day 6
🔧6'. buy on day 6 and found that we cannot sell on day 7
🔧7'. buy on day 7 and sell on day 8
🚧 The real transactions we do are: 🚧
🔧1. buy on day 1 and sell on day 5 (merge 1'~4', we won’t really buy and sell on the same day, since that day will be merged)
🔧2. buy on day 7 and sell on day 8 (same as 7')
We just break down the transaction and keep searching for the best day to sell. We will stop break down one transaction once we found that we cannot “extend the profit” of this transaction.
The time complexity is O(n) and space complexity is O(1).
