Best Time to Buy and Sell Stock

发表于   |  
  • Best Time to Buy and Sell Stock
  • Best Time to Buy and Sell Stock II
  • Best Time to Buy and Sell Stock III
  • Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

题目大意是：
有一个数组记录着一支股票的价格变化，第i个元素表示该股票在第i天的价格。
现在你最多只能对这支股票做一次操作(买入和卖出各一次)，设计一个算法使收益最大。
(吐槽一下，一开始都没看懂题目在说什么。)

解题思路：
收益最大的情形是，在最低价时买入，最高价时卖出。
用一个变量记录最小值，收益为当天价格减去最小值，更新最大收益。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProfit(int[] prices) {
       if (prices.length == 0)
           return 0;
       int minStock = prices[0], maxProfit = 0;
       for (int i = 1; i < prices.length; i++) {
           if (prices[i] < minStock)
               minStock = prices[i];
           else
               maxProfit = Math.max(maxProfit, prices[i] - minStock);
       }
       
       return maxProfit;
   }

Best Time to Buy and Sell Stock II

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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

这次不限制交易次数，但要注意在对股票二次买入前，要先把它卖掉。
思路是：
在买入股票后，直到它不再涨价时再卖出(prices[i] > prices[i+1]时)，可以理解为数组中所有递增子串两端的差值。
直接遍历数组，遇到递增情况就加上差值，相当于延后一天卖出；若递减则不操作。
e.g. prices = {1, 2, 3, 4, 2, 3}, 在价格为1时买入，然后在4时卖出，2时买入，3时卖出。

1
2
3
4
5
6
7
8
public int maxProfit(int[] prices) {
       int maxProfit = 0;
       for (int i = 1; i < prices.length; i++) {
           if (prices[i] > prices[i-1])
               maxProfit += (prices[i] - prices[i-1]);;
       }
       return maxProfit;
   }

Best Time to Buy and Sell Stock III

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

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 at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

最多只能做两次交易。
因为两次交易的作用域不能重叠，所以可以看做对于第i天，一次操作是在[1,i)天内做的，另一次是在[i,N]天做的。然别对两个作用域做求最大收益的操作(即第一题)。
这时的复杂度是0(n^2)，然后成功超时了。。。

其实不用对每个i都求一次最大收益的，求profit[i]时，profit[i-1]已经求过了，就不用再求一次了。
设两个数组分别记录左作用域和右作用域在每一天的最大收益。
left[i]记录[1,i]天的最大收益，right[i]记录[i,N]天的最大收益。
最后再遍历一次数组就可以了。 复杂度O(n)。
e.g.
prices = {1, 2, 3, 4, 2, 3}
left = {0, 1, 2, 3, 3, 3}
right = {3, 2, 1, 1, 1, 0}
profit = {3, 3, 3, 4, 4, 3}
maxProfit = 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int maxProfit(int[] prices) {
       if (prices.length == 0)
           return 0;
       int[] left = new int[prices.length];
       int[] right = new int[prices.length];
       int min = prices[0], max = prices[prices.length-1];
       
       for (int i = 1; i < prices.length; i++) {
           left[i] = Math.max(left[i-1], prices[i] - min);
           min = Math.min(min, prices[i]);
       }
       
       for (int i = prices.length-2; i >= 0; i--) {
           right[i] = Math.max(right[i+1], max - prices[i]);
           max = Math.max(max, prices[i]);
       }
       
       int maxProfit = 0;
       for (int i = 0; i < prices.length; i++)
           maxProfit = Math.max(maxProfit, left[i]+right[i]);
       return maxProfit;
   }

还有一种思路是基于第四题，即k为2的情况。

Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

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 at most k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

好吧，这题还不是很理解，再研究一下。
// To be done …
参考链接

直接解的时候内存溢出了，因为k太大了。
其实可以发现，当k超过数组长度的一半时，就相当于回到了第二题，因为每一天都能做交易。
对于k >= N/2的，直接调用第二题的函数。
k比较小的，则使用动规。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int maxProfit(int k, int[] prices) {
       if (k >= prices.length/2)
           return stockII(prices);
           
       int[] local = new int[k+1];  
       int[] global = new int[k+1];  
       
       for (int i = 0; i < prices.length - 1; i++)  
       {  
           int dis = prices[i+1] - prices[i];  
           for (int j = k; j >= 1; j--)  
           {
               local[j] = Math.max(global[j-1] + Math.max(dis, 0), local[j] + dis);  
               global[j] = Math.max(local[j], global[j]);  
           }  
       }  
       return global[k];  
   }
   
   public int stockII(int prices[]) {
       int maxProfit = 0;
       for (int i = 1; i < prices.length; i++)
           if (prices[i] > prices[i - 1])
               maxProfit += prices[i] - prices[i - 1];
       return maxProfit;
   }