LeetCode 121 - Best Time to Buy and Sell Stock
LeetCode - Best Time to Buy and Sell Stock II
LeetCode - Best Time to Buy and Sell Stock III
LeetCode 188 - Best Time to Buy and Sell Stock IV
Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown
LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
LeetCode - Best Time to Buy and Sell Stock II
LeetCode - Best Time to Buy and Sell Stock III
LeetCode 188 - Best Time to Buy and Sell Stock IV
Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown
LeetCode 714 - Best Time to Buy and Sell Stock with Transaction Fee
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
Say you have an array 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).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/
To avoid multiple simultaneous transactions, we consider buying the stock on dayi and selling it on day i+1 . If this brings in profit, i.e. price[i]<price[i+1] , we do it. If that is the case, Otherwise, we are safe to move to the next day, since we can buy the stock at a price not greater than that on day i .
To avoid multiple simultaneous transactions, we consider buying the stock on day
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0)
return 0;
int maximumProfit = 0; // Maximum profit up to now
// If buying the stock on day i and selling it on day i+1 brings in profit, do it.
// The only possible scenario that withdraws it is that buying on day i+1 and selling
// it on day i+2 also brings in profit. In that case it is equivalent to buying it
// on day i and selling it on day i+2
for (int i = 0; i < prices.length-1; i++)
maximumProfit += Math.max(prices[i+1]-prices[i], 0);
return maximumProfit;
}
http://www.cnblogs.com/grandyang/p/4280803.html
道题由于可以无限次买入和卖出。我们都知道炒股想挣钱当然是低价买入高价抛出，那么这里我们只需要从第二天开始，如果当前价格比之前价格高，则把差值加入利润中，因为我们可以昨天买入，今日卖出，若明日价更高的话，还可以今日买入，明日再抛出。以此类推，遍历完整个数组后即可求得最大利润
http://maxinrui.com/index.php/2018/05/14/122-best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/discuss/39404/Shortest-and-fastest-solution-with-explanation.-You-can-never-beat-this.
https://xuezhashuati.blogspot.com/2017/04/lintcode-149-best-time-to-buy-and-sell_12.html
可以无限次买卖，那么我们从左往右遍历数组，只要发现股价有波动（前一天的价格比今天的低），我们就在前一天买，今天卖。
遍历完数组以后，获利的总和，就是在可以无限买卖的情况下获得的最大利润。
道题由于可以无限次买入和卖出。我们都知道炒股想挣钱当然是低价买入高价抛出，那么这里我们只需要从第二天开始，如果当前价格比之前价格高，则把差值加入利润中，因为我们可以昨天买入，今日卖出，若明日价更高的话，还可以今日买入，明日再抛出。以此类推，遍历完整个数组后即可求得最大利润
http://maxinrui.com/index.php/2018/05/14/122-best-time-to-buy-and-sell-stock-ii/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/discuss/39404/Shortest-and-fastest-solution-with-explanation.-You-can-never-beat-this.
For Buy and Sell 1, we were limited to 1 transaction, so we had to find the largest sum of contiguous ints in an array of price differences.
Q: Why does finding the most profitable transaction boils down to finding the largest sum of contiguous ints in the array of price differences?
A: Define D[i] = Prices[i] - Prices[i-1] (difference between 2 consecutive prices)
D[i] is essentially a "delta" trade.
A transaction is defined as buying at Prices[X] and selling at Prices[Y],
the profit of the transaction
= Prices[Y] - Prices[X]
= Prices[Y] - Prices[Y-1] +
Prices[Y-1] - Prices[Y-2] ...
....
Prices[X+1] - Prices[X]
= D[Y] + D[Y-1] + ... + D[X+1]
= sum of D from X+1 to Y
The problem is to find max(Prices[Y] - Prices[X]) which is equivalent to finding the largest sum of contiguous D's.
To illustrate, if D[Y+1] is positive, it means Prices[Y+1] > Prices[Y], which implies I should sell at Prices[Y+1] instead of Prices[Y]. Basically it means I just add D[Y+1] to D[Y] + ... + D[X+1].
Note that there could be a negative or zero D in the best running sequence. It doesn't matter so long the sum of the sequence is the largest.
Now we are allowed unlimited transactions. So if there is a negative D, we could just break the sequence into 2, that is, into 2 transactions so as to avoid the negative element.
This boils the whole problem down to adding up all positive sums of contiguous ints in D, which simplifies to just adding up all the positive ints
https://xuezhashuati.blogspot.com/2017/04/lintcode-149-best-time-to-buy-and-sell_12.html
可以无限次买卖，那么我们从左往右遍历数组，只要发现股价有波动（前一天的价格比今天的低），我们就在前一天买，今天卖。
遍历完数组以后，获利的总和，就是在可以无限买卖的情况下获得的最大利润。
public int maxProfit(int[] prices) { if (prices == null || prices.length == 0) { return 0; } int maxProfit = 0; for (int i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { int thisProfit = prices[i] - prices[i - 1]; maxProfit += thisProfit; } } return maxProfit; }http://blog.unieagle.net/2012/12/04/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abest-time-to-buy-and-sell-stock-ii/
int maxProfit(vector&prices) { int p = 0; for(int i = 1; i < prices.size() ; ++i) { int delta = prices[i] - prices[i-1]; if(delta > 0 ) { p += delta; } } return p; }
X. Local Min/Max
时间复杂度:O(n)，空间复杂度O(1)。思路和上述差不多，但是是模拟股票交易过程。外层while循环控制整个数组遍历，内层第一个while循环首先找出第一个低谷，找到后，令valley为低谷的值；第二个while循环从低谷处出发开始寻找峰顶处，如果一直升高，则i一直增加下去，峰顶值赋给peak。这样，找到的一对【低谷，峰顶】值差就是maxprofit。之后继续这个过程
时间复杂度:O(n)，空间复杂度O(1)。思路和上述差不多，但是是模拟股票交易过程。外层while循环控制整个数组遍历，内层第一个while循环首先找出第一个低谷，找到后，令valley为低谷的值；第二个while循环从低谷处出发开始寻找峰顶处，如果一直升高，则i一直增加下去，峰顶值赋给peak。这样，找到的一对【低谷，峰顶】值差就是maxprofit。之后继续这个过程
The greedy pair-wise approach mentioned in other posts is great for this problem indeed, but if we're not allowed to buy and sell stocks within the same day it can't be applied (logically, of course; the answer will be the same). Actually, the straight-forward way of finding next local minimum and next local maximum is not much more complicated.
public int maxProfit(int[] prices) {
int profit = 0, i = 0;
while (i < prices.length) {
// find next local minimum
while (i < prices.length-1 && prices[i+1] <= prices[i]) i++;
int min = prices[i++]; // need increment to avoid infinite loop for "[1]"
// find next local maximum
while (i < prices.length-1 && prices[i+1] >= prices[i]) i++;
profit += i < prices.length ? prices[i++] - min : 0;
}
return profit;
}
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/discuss/208241/Explanation-for-the-dummy-like-me
The profit is the sum of sub-profits. Each sub-profit is the difference between selling at day
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
3. Update the solution (Increment count of buy sell pairs)
4. Repeat the above steps if end is not reached.
Read full article from LeetCode - Best Time to Buy and Sell Stock II | Darren's Blog
The profit is the sum of sub-profits. Each sub-profit is the difference between selling at day
j, and buying at day i (with j > i). The range [i, j] should be chosen so that the sub-profit is maximum:sub-profit = prices[j] - prices[i]
We should choose
j that prices[j] is as big as possible, and choose i that prices[i] is as small as possible (of course in their local range).
Let's say, we have a range
Now, if we add
[3, 2, 5], we will choose (2,5) instead of (3,5), because 2<3.Now, if we add
8 into this range: [3, 2, 5, 8], we will choose (2, 8) instead of (2,5) because 8>5.
From this observation, from day
X, the buying day will be the last continuous day that the price is smallest. Then, the selling day will be the last continuous day that the price is biggest.
Take another range
Similarly,
Actually, the range
[3, 2, 5, 8, 1, 9], though 1 is the smallest, but 2 is chosen, because 2 is the smallest in a consecutive decreasing prices starting from 3.Similarly,
9 is the biggest, but 8 is chosen, because 8 is the biggest in a consecutive increasing prices starting from 2 (the buying price).Actually, the range
[3, 2, 5, 8, 1, 9] will be splitted into 2 sub-ranges [3, 2, 5, 8] and [1, 9].
We come up with the following code:
public int maxProfit(int[] prices) {
int i = 0, buy, sell, profit = 0, N = prices.length - 1;
while (i < N) {
while (i < N && prices[i + 1] <= prices[i]) i++;
buy = prices[i];
while (i < N && prices[i + 1] > prices[i]) i++;
sell = prices[i];
profit += sell - buy;
}
return profit;
}
The time complexity is
O(N), space complexity is O(5)BONUS:
With this approach, we still can calculate on which buying days and selling days, we reach the max profit:
public Pair<List<Pair<Integer, Integer>>, Integer> buysAndSells(int[] prices) {
int i = 0, iBuy, iSell, profit = 0, N = prices.length - 1;
List<Pair<Integer, Integer>> buysAndSells = new ArrayList<Pair<Integer, Integer>>();
while (i < N) {
while (i < N && prices[i + 1] <= prices[i]) i++;
iBuy = i;
while (i < N && prices[i + 1] > prices[i]) i++;
iSell = i;
profit += prices[iSell] - prices[iBuy];
Pair<Integer, Integer> bs = new Pair<Integer, Integer>(iBuy, iSell);
buysAndSells.add(bs);
}
return new Pair<List<Pair<Integer, Integer>>, Integer>(buysAndSells, profit);
}
public class Pair<T1, T2> {
public T1 fst;
public T2 snd;
public Pair(T1 f, T2 s) {
fst = f;
snd = s;
}
}1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
3. Update the solution (Increment count of buy sell pairs)
4. Repeat the above steps if end is not reached.
void stockBuySell(int price[], int n){ // Prices must be given for at least two days if (n == 1) return; int count = 0; // count of solution pairs // solution vector Interval sol[n/2 + 1]; // Traverse through given price array int i = 0; while (i < n-1) { // Find Local Minima. Note that the limit is (n-2) as we are // comparing present element to the next element. while ((i < n-1) && (price[i+1] <= price[i])) i++; // If we reached the end, break as no further solution possible if (i == n-1) break; // Store the index of minima sol[count].buy = i++; // Find Local Maxima. Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i-1])) i++; // Store the index of maxima sol[count].sell = i-1; // Increment count of buy/sell pairs count++; } if (count == 0) printf("There is no day when buying the stock will make profit\n"); else { for (int i = 0; i < count; i++) printf("Buy on day: %d\t Sell on day: %d\n", sol[i].buy, sol[i].sell); } return;}