一、数组i位置代表第i天股票的价格，只允许，买一次，卖一次，买卖不可以在同一天，求最大利润。
【Best Time to Buy and Sell Stock系列】思路：第0天买，找比第0天价格高的最多的一天卖出，得到第0天买入的最大利润；以此类推，得到n-1个最大利润，求其中的最大值，即满足题目要求。
这个算法的复杂度分析：
n-1+n-2+n-3+.....+1=n(n-1)/2时间复杂度是O(N^2)
空间复杂度为O（1）
必然可以简化算法。
记录当前最小值，用当前值减去最小值，得到的利润与当前最大利润比较。
就是如果后者比前者大，那后者肯定不是买入的那一天，也就不用去算那天买入时的最大利润。
复杂度分析：
时间复杂度O(N) 因为只遍历了一次
空间复杂度还是常数
有两种写法：
直观法：
文章图片
巧妙法：Kadane's Algorithm算是一种简单的动态规划
https://en.wikipedia.org/wiki/Maximum_subarray_problem
遇到比当前最大利润买入股价要小的，就从这天买入计算最大利润，最后进行比较。
文章图片
二、可以买卖多次，求最大利润。
思路：只要后者大于前者，就可以进行一次买卖。同一天可以同时买卖。
复杂度分析：
时间复杂度，O(N)
空间复杂度，O(1)
文章图片
三、只能进行两次买卖 还是动态规划k次交易 令k=2
https://blog.csdn.net/linhuanmars/article/details/23236995
时间复杂度：2N ,O(N)
空间复杂度：O（1）
文章图片
为什么要倒序？因为要用到上一天的max_cur[j-1],所以j不能先更新小的
四、只能k次但是用以上方法，内存出错
空间复杂度 O(N)
文章图片
文章图片
五、Best Time to Buy and Sell Stock with Cooldown
可以进行多次交易，但是这一天卖出去，需要冷静一天，再进行买卖。
https://soulmachine.gitbooks.io/algorithm-essentials/java/dp/best-time-to-buy-and-sell-stock-with-cooldown.html
其实与二相似，buy 是一天 然后后边选择连续两天，sell+cooldown.
那么需要维护两个数组，
sell【i】第i天手里没股票的zui大利润，今天卖了股票或者，没动作。
buy[i] 第i天手里有股票，今天买了股票，或者之前买的，今天不卖。
那sell[i]=max(prices[i]+buy[i-1],sell[i-1])
buy[i]=max(buy[i-1],sell[i-2]-prices[i])
最终手里没股票。sell[n-1]
时间复杂度：O(N）
空间复杂度：O(N)
文章图片
可以优化空间复杂度，因为sell,只与前一个有关，buy只与前两个有关。
文章图片
六、每次卖要给交易费
在二的基础上增的限制，是多次交易减去交易费，但是用二的做法，并不能知道交易多少次。
http://www.cnblogs.com/grandyang/p/7776979.html
文章图片
推荐阅读
- 笔记|如何在Windows11安装安卓子系统（）
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 2021年下半年《信息系统项目管理师》真题
- 个人理解|【C语言基础之类型转换】
- 学习分享|【C语言函数基础】
- 个人理解|【C语言实现井字棋及电脑落子优化】
- Python|蓝桥杯 平面切割 Python
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 笔记|这是一个关于face_recognition和dlib库的安装（亲测有用，毕竟我代码都写出来了）
- 信令模式与非信令模式