image.png
题目：给定一个数组，第i个元素为第i天的股票价格，如果至多只能完成一个交易（买一个和卖一个），设计一个算法找到最大的收益。
注意：要在买了股票之后才能卖出
思路一：两次遍历寻找前后两个数的最大差值，运行结果超时，时间复杂度O(n^2)
思路二：遍历一次。初始化最小值为low=prices[0],profit=0。遍历的时候进行判断，判断此时的价格是否低于low，如果低于则现在的价格为low，继续下一次循环；否则，计算当前的价格减去low，为当前的profit。遍历中不断更新这两个值，最终的结果为最大的profit。
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
l=len(prices)
maxp=0
if l==0:
return maxp
else:
low=prices[0]
for i in range(1,l):
if prices[i]<low:
low=prices[i]
else:
profit=prices[i]-low
if maxp<profit:
maxp=profit
return maxp
image.png
题目：这题与121题不同的地方在于，可以进行不止一次的交易，可以进行多次交易使得利益最大。在卖出一只股票之前不能够买入。
解法1：暴力法。只需计算出所有可能的交易集合相应的利润，利润最大的即为最终结果。但是这种做法的时间复杂度为O(n^n)，空间复杂度为O(n)。
解法2：峰谷法。如下图所示，我们可以得知最大的利益是在连续的峰和谷之间的差值之和，即A+B，最高峰减去最低谷的值C，也是小于A+B的，所以，我们应当找到连续的峰和谷，然后计算他们的和。
image.png
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
l=len(prices)
if l==0:
return 0
else:
valley=prices[0]
peak=prices[0]
maxprofit=0
i=0
while i<l-1:
while (i+1<l)and(prices[i+1]<=prices[i]):
i=i+1
valley=prices[i]
#寻找山谷后面的最高峰（在下一个山谷之前）
while (i+1<l)and(prices[i+1]>=prices[i]):
i=i+1
peak=prices[i]
maxprofit=maxprofit+peak-valley
return maxprofit
解法3：这个解决方案遵循了方法2本身使用的逻辑，但是只有轻微的变化。在这种情况下，我们不需要寻找山谷后面的每一个高峰（在下一个山谷之前），而只需继续沿着斜坡爬行，并不断增加从每个连续交易中获得的利润。这一点可以通过下面这个例子来说明:
image.png
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
l=len(prices)
if l==0:
return 0
else:
maxprofit=0
i=0
while i<l-1:
if prices[i+1]>prices[i]:
maxprofit=maxprofit+prices[i+1]-prices[i]
i=i+1
return maxprofit
