Best Time to Buy and Sell Stock II
Best Time to Buy ans Sell Stock
最近越来越觉得编程就是数学问题，数学的逻辑思维决定了写出的程序的质量。在做这道题的时候越发觉得如此。
题目简介
这个题目分为两个系列，分别是I和II，其中I是II的简单版本。
刚做I时感觉很简单，对于O(n^2)和O(n)时间复杂度的版本能够很快给出解决方法。但是对于II，第一眼看过去并没有明显的思路，于是乎就耐心研究了起来。
解题方法
首先是分析卖出条件
假设一列数据[a1, a2, …, ax, …, aa, ab, …, ac, …]，在aa之前已经买入为ax，根据题目要求可值，ax只有一个
ax的限制要求
在(ax,…, aa]范围内，ax应该都是最小的，如果存在ay < ax,则ax的收益肯定比ay少，则买入点ay肯定比ax要更优。
卖出点要求
现在状态是： ax是买入点，现在需要判断是aa点是否可以卖出？
考虑[ax, …, ac]之间的收益
- 若ac为卖出点时，整个区间的收益为：ac – ax
- 若中间某点卖出，然后再买入，区间收益为：aa – ax + ac – ab
由于要使收益最大化，因此：
aa – ax + ac – ab > ac – ax ==> aa > ab
也就是说，只要aa大于ab即可卖出，以使得收益最大化，根据这点即可写程序获取到改题的求解方法。相应的代码放在GitHub上了，欢迎提改进意见。
总结
解决问题遇到没有思路时，好好分析中间条件，可以更有助于捋顺思路。还是要好好学习数学啊！
版权声明：本文为chinazhonghao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。