Buy and sell stocks 总结

buy and sell stocks 在leetcode现在总共有5 道题。

这道题是基础，只能transaction一次，所以我们用

这道题表示可以一直transaction，所以只需要下一次比上一次高，那就加一次。

这道题属于进化版, 参考大神的解释：Best time to buy and sell stock with cooldown

交易2次还是3次是一样的，一直可以到K次。定义连个数组，local[i][j]表示在第i天的时候交易了j次的最有local解；global[i][j]表示在第i天的时候交易j次的最优解。

迭代方法是

dif = prices[i+1] - prices[i];

local[i][j] =Math.Max( global[i-1][j-1]+Math.Max(dif,0) , local[i-1][j]+dif);

global[i][j] = Math.Max(global[i-1][j], local[i][j]);

其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值后相比，两者之中取较大值，而全局最优比较局部最优和前一天的全局最优。

但这道题还有个坑，就是如果k的值远大于prices的天数，比如k是好几百万，而prices的天数就为若干天的话，上面的DP解法就非常的没有效率，应该直接用无限次transaction的方法来求解，所以实际上这道题是II和III综合体。