[LeetCode]122. Best Time to Buy and Sell Stock II

Description:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

————————————————————————————————————————————————————————————————————————————

Solution:

有三种方法：

1.暴力算法：最容易想到，但是会TLE

2.峰谷算法：找到每个“峰”和“谷”（即局部最大值和局部最小值），相邻的峰谷相减，将结果累加到maxProfit上即可。参考Solution：

3.上坡算法：第二种算法的简化，不需要找到峰谷，只需要在遍历中判断当前值和上一个值的大小，若当前值大，则相减，将结果累加到maxProfit中；若当前值小，则跳过。参考Solution：