买卖股票的最好时机I

读前福利，送大家一些电子书

买卖股票的最好时机I

LeetCode 121. 买卖股票的最佳时机

问题描述：

给定一个数组prices，它的第i个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例：

输入：[7,1,5,3,6,4]

输出：5

解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

分析问题：

​ 拿到这个问题，我们就需要先思考用什么样的思想去解决。我们来看这个题目，这个问题是求最优解问题。初看题目，我们最容易想到的方法，就是暴力求解，即遍历数组，求出最大值和最小值，相减就是最大利润。不过这里有一个隐含条件，就是股票的卖出时机必须大于股票的买入时机。

def maxProfit(prices):
    #最大利润
    ans = 0
    #股票卖出时机要大于股票买入时机
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            ans = max(ans, prices[j] - prices[i])
    return ans

prices=[7, 1, 5, 3, 6, 4]
maxProfit(prices)

​ 我们可以看出，这种求解的方法，时间复杂度是O(n^2)，那有没有时间复杂度更优的方法呢？

​ 首先，我们来分析一下这个问题符合什么“问题模型”呢？我们从0开始走，走到n-1，一共需要走n-1步，也就对应着n-1个阶段。每个阶段都只能往右走，并且每个阶段都会对应一个状态集合，我们把状态定义为maxprofit[i]，其中i表示走到哪一步，maxprofit[i]的值表示从开始走到位置i的最大利润是多少。所以这个问题是“多阶段决策最优”问题，对于这类问题，我们首先要考虑能否用动态规划的思想来解决，也就是看是否符合动态规划的特征：重复子问题、无后效性、最优子结构。

1. 无后效性：我们要想计算maxprofit[i]这个状态，只需要关心maxprofit[i-1]的状态，并不关心maxprofit[i-1]这个状态是如何生成的。而且，我们只能往后移动，不允许后退。所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变。所以符合"无后效性"。

2. 重复子问题：如果要达到maxprofit[i]这个状态，我们可以有不同的决策序列。比如假设第五天，我们的最大利润是8，即maxprofit[i]的状态为8，我们可以是第一天买入2，第三天卖出10。也可以第二天买入2，第三天卖出10。

3. 最优子结构：因为maxprofit[i]可以通过maxprofit[i-1]推导出来，即符合“最优子结构”

   maxprofit[i]=max(maxprofit[i-1],prices[i]-minprice)
   

   下面我们看代码如何实现：

def maxProfit(prices):
    n=len(prices)
    if n==0:
        return 0
    maxPRofit=[0]*n
    minprice=prices[0]

    for i in range(1,n):
        minprice = min(minprice, prices[i])
        maxPRofit[i]=max(maxPRofit[i-1],prices[i]-minprice)

    return maxPRofit[-1]

prices=[7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

​ 我们可以看出，这种求解的时间复杂度为O(n)。