122. 买卖股票的最佳时机 II

背景：只能持有一股，买卖无数次。保证收益最大化。

解法一：搜索，DFS 深度搜索。

每天可以有两个操作：

1. 买一股
2. 卖一股

遍历每个元素，记录买一股买一股的收益，递归的找出收益最大的操作。

时间复杂度：O(2ⁿ)

解法二：贪心算法

思想：只要后一天的价格比前一天的价格高，那么就在前一天买进，后一天卖出即可。

决定是否可行条件：是否可在同一天进行买进与卖出。同时无交易手续费，所以可以频繁交易。

实现：写一层循环，判断后一天比前一天高时，在前一天买进，后一天卖出即可。然后把所有的收益加上即可。

时间复杂度：O(N)

解法三：动态规划 DP

把每一天之前的这个状态都记下来，也就是针对每一种天数列一个状态，这个状态是：以后1股的时候利润是多少，0股的时候利润是多少，把最大的利润保存好。然后每天就和前面的这一天进行对比，是卖出还是买进。

时间复杂度：O(N)

动态规划可解决的问题，比贪心多。但老师这节课并不是主要讲这个。

详细题解：暴力搜索、贪心算法、动态规划