1 题目描述

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。


输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

2 题目分析

2.1 贪心

因为我们已经有了预知能力，只有明天的价格比今天高，就有利可图，我们就买今天的股票，然后到明天再卖出。则利润为prices[i+1]-prices[i],到最后一天（以后的那些天价格都没有这一天价格高了，即峰值），我们会将昨天preices[j-1]拥有的股票以今天的价格prices[j]卖出,那么获得的利润prices[j]-prices[j-1],然后再也不买股票了(明天的价格比今天高 这个条件再也不符合了)。

说人话就是，只要今天的价格比昨天高，你只管往出卖就有钱赚，具体哪一天买卖操那闲心干啥。

贪心算法在此的本质是吸取正利润区间，也就是今天价格比昨天高的这种小区间

    def maxProfit(self, prices) -> int:

        # 贪心
        res = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                print(prices[i-1],prices[i],i)
                res += prices[i] - prices[i - 1]
        return res

2.2 动态规划

动态规划的重点在于寻找状态转移方程，那么我们就第i的状态作以分析。

在第i天，股票的状态有两种，持有和没有。而每种状态小分两个小情况。我们以dp[i][0]来表示持有的状态时的最大利润，dp[i][1]来表示不持有的状态时的最大利润。

持有
1. 昨天就持有，今天没有卖出，
  
  那么目前的利润是昨天有的时的最大利润， dp[i-1][0]
2. 昨天没有的，今天新买的
  
  那么目前的利润是昨天不持有时的最大利润 - 今天的支出， dp[i-1][1] - prices[i]
不持有
1. 昨天就没有，今天也没有买
  
  那目前的利润就是昨天没有时的最大利润， dp[i-1][1]
2. 昨天有的，今天卖掉了
  
  那目前的利润就是昨天有时的最大利润 + 今天卖出的， dp[i-1][0] + price[i]

通过上面的分析，我们得到了状态转移方程，那么什么最后的我需要的状态时怎样的，肯定时把手里股票卖干净时的状态。即dp[n][1],

同时，初始状态应该时怎样的，第1天不持有股票故让dp[0][1]=0, 第一天持有股票则dp[0][0] = - preices[0](即第一天买了股票)

根据上面的分析，我们可以写处如下的代码：

    def dp_method(self, prices):
        prices_len = len(prices)
        dp = [[0] * 2 for i in range(prices_len)]

        # init dp[0]
        dp[0][0], dp[0][1] = -prices[0], 0

        for i in range(1, prices_len):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])

        return dp[prices_len - 1][1]

上面的代码种，我们要开辟一个n*2的list，但是实际上我们用四个变量不断覆盖就能完成更新操作，改进的代码如下。

    def dp_method2(self, prices):

        dp_has, dp_noHas = -prices[0], 0

        for i in range(1, len(prices)):
            dp_has_new = max(dp_has, dp_noHas - prices[i])
            dp_noHas_new = max(dp_noHas, dp_has + prices[i])

            dp_has = dp_has_new
            dp_noHas = dp_noHas_new
        return dp_noHas