Facebook 新题

best time to sell stock II，允许sell无限多次，但是每次sell都要给3$的代价，问说如何获得最大的profit。希望大家一起讨论讨论

我给一个思路吧（虽然还不能严格证明正确性）。希望抛砖引玉：

首先，我们肯定不会在非“谷值”的地方买入，也不会在非“峰值”的地方卖出。所以，为了简化问题，我们先提取出这个序列中所有的“谷值”和“峰值”。分别存放于队列A和B中。

接下来，这个问题和Stock II的唯一区别就在于每次交易要收取佣金，所以使得有时候多次连续交易来得不如合并成一次划算。比如[1->20, 18->30]两次交易=>19-3 + 12-3 = 25，就不如[1->30]一次交易=>30-1-3=26来得划算。

假设第i次交易的始终价格分别为(Ai, Bi)，而第i+1次交易为(Ai+1, Bi+1)；那么，
当两交易的profit都>=3时，
分开交易的收益是
Bi+1-Ai+1 + Bi-Ai - 6而合起来交易的收益是
Bi+1-Ai -3
所以，如果两次交易应该合并，则必有：
Bi+1-Ai -3 >= Bi+1-Ai+1 + Bi-Ai - 6
即
Bi - Ai+1 <= 3 ....... (a)

如果仅有第二个交易的profit小于3，那么上述条件(a)是不充分的，比如[1 -> 100]，[98 -> 99]这种情况本来不应该合并。所以，此时还应检查是否有
Bi+1 >= Bi ...... (b)

如果仅有第一个交易的profit小于3，那么(a), (b)也是不充分的，比如[2 -> 3], [1 -> 100]这种情况不应合并。所以，此时应检查是否有
Ai+1 >= Ai ...... (c)

如果两个交易的profit都<=3，那么此时无论两个交易的始末值如何，总是可以合并。因为，如果合并后的profit依然<3，甚至变为负值，那么我们可以在最后的postprocessing步骤忽略掉这次交易；如果合并后的profit>3，那么我们本来就应该合并这两次交易。所以合并总是正确的选择。


综上所说，我们能够合并两次交易的充分条件是(a) & (b) & (c).

所以，我们依次取出A和B中每一对元素(Ai, Bi)，检查它们和上一对元素(Ai-1, Bi-1)是否满足这个关系。如果是的话，则合并二者为(Ai-1, Bi)，不是的话则二者均保留。然后继续检查下一对元素。

在合并时，每个范围最多会被合并一次。比如(A3, B3)如果已经被合并到(A4, B4)中去，那么以后就不会再单独检查(A3, B3)了。相当于每个范围最多被删除一次。所以最后总时间应该仍然是O(N)。

最后，统计没有被合并的范围的个数。如果其中出现profit<3的交易，则认为其profit为0（即不进行此次交易）。

代码如下：

1. int getMaxProfitV(vector<int>& prices)
   
2. {
   
3.     int N = prices.size();
   
4.     queue<int> A, B;
   
5.     // 找到所有峰值和谷值
   
6.     for (int i = 0; i < N; ++i) {
   
7.         int left = (i == 0)? INT_MAX: prices[i-1];
   
8.         int right = (i == N-1)? INT_MIN: prices[i+1];
   
9. 
   
10.         if (left <= prices[i] && prices[i] > right) {
    
11.             B.push(prices[i]);
    
12.         }
    
13.         else if (left > prices[i] && prices[i] <= right) {
    
14.             A.push(prices[i]);
    
15.         }
    
16.     }
    
17. 
    
18.     stack<pair<int, int> > res;
    
19.     res.push(pair<int, int>(A.front(), B.front()));
    
20.     A.pop(); B.pop();
    
21.    // 维护一个stack。每次新处理一次交易，就试图将此次交易与栈顶的交易合并，直到不能合并为止。
    
22.     while (!A.empty()) {
    
23.         int lo = A.front(), hi = B.front();
    
24.         A.pop(); B.pop();
    
25. 
    
26.         // 虽然是二重循环，但是push操作只进行了N次，所以pop操作也最多只能进行O(N)次。最后总时间依然是O(N)。
    
27.         // (a), (b), (c) 三条件必须都满足
    
28.         while (!res.empty() &&
    
29.                 res.top().first <= lo &&
    
30.                 res.top().second - lo <= 3 &&
    
31.                 res.top().second <= hi
    
32.                ) {
    
33.             lo = res.top().first;
    
34.             res.pop();
    
35.         }
    
36.         res.push(pair<int, int>(lo, hi));
    
37.     }
    
38.     int sum = 0;
    
39.     // 最后统计所有的范围，<3的则看做0.
    
40.     while(!res.empty()) {
    
41.         pair<int, int> cur = res.top(); res.pop();
    
42.         cout << cur.first << ", " << cur.second << endl;
    
43.         if (cur.second - cur.first > 3) {
    
44.             sum += cur.second - cur.first - 3;
    
45.         }
    
46.     }
    
47.     return sum;
    
48. }

复制代码

代码看起来有点丑是真的。我猜这题应该也可以通过类似于其他stock题那样用DP来做，不过我还没想到具体解法。

returning 发表于 2016-3-21 01:52
我隐约感觉这道题你想复杂了，题目并不是lc上的stock II，题目是说你可以在某天sell多次。lc上的题每天是 ...

确实这道题可能说得略模糊，我的解法也只是个人理解。我的理由是，

1. lz先说了“best time to sell stock II”这句话，我认为他想表达的是：“一切假设都和Stock II一样，唯一的不同是。。。”，其中包括“不得同时持有多股”这一点。

2. 如果你的理解是正确的，那么题目中必须加入两个关键表述：“能够同时持有多股”和“每次卖出能卖一股/多股”。我认为lz表述时不会漏掉这么多关键信息，所以我倾向于认为这两个假设一开始就不存在。另外lz原话是“可以sell无限次”，并非“可以在同一天内sell无限次”。

3. 按你的理解，此题难度会低得多。可能甚至低于Stock I。这种情况下，我认为lz一开始就不会出来问这道题；况且这种难度的题对于Facebook的申请者来说区分度较低，不太适合。


其实，无论咱们现在怎么理解这道题并不重要，关键问题是如果真的面试时问出了按我的理解方式的题，是否能快速答出来呢？

milanelllo13 发表于 2015-7-8 12:43
这道题，我问过我一个同学。  他给的思路是：  这个题就是找很多对相邻的极小值和极大值点。  然后某一对极 ...

咱们判断算法正确性可不能靠感觉啊。考虑下面这个例子：
[1 9 8 100]

四个点中有两个极大，两个极小点，共两次交易，每次的profit都大于佣金。所以如果按这个算法，总利润是

9-1 - 3 + 100-8 - 3 = 8 + 92 - 6= 94

但是事实上这个例子的最大profit是一次交易：

100 - 1 -3 = 99 - 3 = 96

所以这题的难点是在于考虑合并多次交易的情况（见上上楼）。

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {

        if(prices.empty() || prices.size() == 1)
        {
            return 0;
        }

        int maxProfit = 0;
        int localProfit = 0;
        for(int i = 1; i < prices.size(); i++)
        {
            if(prices[i - 1] < prices[i])
            {
                localProfit += prices[i] - prices[i - 1];
            }
            else
            {
                if(localProfit >= 3)
                {
                    maxProfit += localProfit - 3;
                }
                localProfit = 0;
            }
        }
        return maxProfit;
    }
};

tangchensr 发表于 2015-7-4 09:40
class Solution
{
public:

这个程序应该不行。

首先，代码中有点问题：如果prices如果一直是上升的，那么maxProfit就永远不会得到更新，所以最后一定会返回0。所以在循环结束以后应该再更新一次maxProfit；

其次，即使这样做了，这个算法也是不对的。因为，最大的profit未必是每个序列单独的profit之和。比如[1, 3, 2, 100]这个序列。你的算法中会先找到[1, 3]这个上升序列，其profit<=3，所以扔掉；再看[2, 100]这个序列，得到98，减3得95。而事实上这个序列的最大profit应该是100 - 1 - 3 = 96才对。

这道题，我问过我一个同学。  他给的思路是：  这个题就是找很多对相邻的极小值和极大值点。  然后某一对极大值减去极小值大于commission fee，就算一次交易。    感觉是对的！

stellari 发表于 2015-7-8 13:39
咱们判断算法正确性可不能靠感觉啊。考虑下面这个例子：
[1 9 8 100]

谢谢。他有和我说过 要和前一次合并。。我自己给忘记了。。   谢谢哈哈哈

stellari 发表于 2015-7-4 15:51
我给一个思路吧（虽然还不能严格证明正确性）。希望抛砖引玉：

首先，我们肯定不会在非“谷值”的地方买 ...

我同意你的看法。
我的想法是遍历数组，找increasing sub list，然后把这个sublist的 （min，max）存到stack里，
在继续找下一个increasing sub list，再与stack顶部的（min，max）合并。

其实这道题像是merge intervals的变种

当有收益时候竟可能的让收益最大再卖掉.

stellari 发表于 2015-7-4 15:51
我给一个思路吧（虽然还不能严格证明正确性）。希望抛砖引玉：

首先，我们肯定不会在非“谷值”的地方买 ...

我隐约感觉这道题你想复杂了，题目并不是lc上的stock II，题目是说你可以在某天sell多次。lc上的题每天是没法buy or sell多次的。比如如下数组[1, 3, 15,20]，最佳收益是20-1 + 20-3 + 20-15， 也就是说每天都买，但是最后一天卖出。所以，如果加上限制条件，那就只需要考虑当前和最大的差值是否少于3，如果少于3，买了也白买。我觉得这样就够了。