在一个股票交易中，以1元的本金在一个连续的M天中进行买卖，可能获得的最高收入是多少？并且在理想收入中允许有非正数股票的买卖。
现在已知股票在第i天的价格是V[i] ， 1<=i<=M ,求M天后的理想收入。
碰见这种最优化问题第一反应还是尝试动态规划：
1.较直观的动态规划：
首先我们定义F[i] 表示在第i天能通过前i天的买卖最后获得的最大收入，其实也就是第i天手上的钱，因为我们只考虑从到第i天，所以当天手上要是还有股票那肯定要全部卖出去对吧。而当天手上可能是没有股票的，可能在之前就已经换成钱了，所以这一部分是F[i-1]， 但也有可能手上全是股票，而这些股票是在第k天的时候把第k天的钱全部换成股票来的，然后再在第i天全部卖出换成钱。所以这部分是 F[ k] / V [k] * V[ i ].
最后 F [i] = Max ( F [ i-1] , F[k] / V[k] * V[i] } , 1<=k<i ;
这个算法复杂度是O(n2)的。
2. 从上一个算法递归公式可以注意到最后的F[i] 第二项是由两部分组成， 一部分是 F [k] / V[k] ，另一部分是V[i]这是不变的，也就是要找使得 F[k]/ V[k]最大的这个k对吧，比如算第i天的时候找到了一个k，然后算第i+1天的时候的k' 要么就是前一个k， 要么是 F[i] / V[i] 对吧，所以很明显是可以用单调队列来优化的~ 一下使得找 F[k] / V[k] 最大的这个K的复杂度从O(n)变成了O(1)，最后的算法复杂度也降到O(n)。
再直白一点来讲，第i天手上能有的最多的钱，当天手上要么是钱，第i天不做买卖，要么全是股票，全在第i天卖出换成钱，所以它取决于前一天的两个变量：1是前一天能有的最多的钱，2是前一天能有的最多的股票，所以我们分别用 F[i] 和 G[i] 来表示这两个维度。
因此 F[i] = max{ F[i-1] , G[i-1] * V[i ] } 。对吧~ 而因为F[i]只与F [i-1] 有关，所以我们用两个变量就可以保存这个信息了，空间复杂度也降为O(1)。