'''
121. Best Time to Buy and Sell Stock
给定输入数组，其中数组的第i个元素表示在第i天货物的价格，第i天可以将货物送出或者买进
但是买入必须要在售出之前，求所能获得的最大利润
如果数组已经是绝对意义上的降序排列(即售出的价格不可能高于买入的价格)，则函数返回0
方法1：暴力搜索，需要的时间复杂度为 O(N**2)
方法2：动态规划，降维成时间复杂度O(N)，
L[i] 表示从第0天到第i天为止，股票的最低价格
P[i] 表示第i天，能够获得的最大收益
状态转移方程：
L[i]=min(L[i-1],prices[i])
P[i]=max(P[i-1],prices[i]-L[i-1])
# 在第i天能够获得的最大收益：等于在前一天能够获得的最大收益和在第i天将股票售出，所能获得的收益
方法3：动态规划
先求出紧邻的元素值之差，即紧邻情况下，在第i+1天售出，在第i天买入的收益，得到数组gain，长度为 length(prices)-1
然后问题转换为求gain数组的最大子序列的和的问题
'''
'''
方法二：
class Solution:
def maxProfit(self, prices) -> int:
if(len(prices)<=1):
return 0
else:
L=[]
L.append(prices[0])
P=[0]
for i in range(1,len(prices)):
L.append(min(L[i-1],prices[i]))
P.append(max(P[i-1],prices[i]-L[i-1]))
return P[len(prices)-1]
'''
'''
方法三：转换成 maxSubArray的问题
class Solution:
def maxProfit(self, prices) -> int:
if(len(prices)<=1):
return 0
else:
gain=[]
dp=[]
max_value=0
for i in range(1,len(prices)):
gain.append(prices[i]-prices[i-1])#求出紧邻元素对之间的价格之差
# print("gain",gain)
# 下面求gain数组中的最大子序列的和
if i==1:
dp.append(max(gain[0],0))
else:
dp.append(max(gain[i-1],dp[i-2]+gain[i-1]))
if dp[i-1]>max_value:
max_value=dp[i-1]
# print('dp',dp,max_value)
return max_value
'''
if __name__=="__main__":
print((Solution().maxProfit([7,1,5,3,6,4])))
