本次分享一道经典的算法题，准确的说是一道题的不同条件下的不同求法。这道题一共有六种情况，每种情况都是不同的解法，在leetcode上对应六道题：

        前两题为这个系列的基础，也是引导之后解法思维方式的关键。

第一题，只能交易一次

        第一题的题目如下：

        在拿到题目之后，首先需要确定的是：买入股票的时候一定在卖出之前，体现在我们的参数上就是买入的时候的价格在数组中的序号是小于卖出的价格在数组中的序号的。

        因为确定了上面的这个思路，所以我拿到题目后首先想到的是：我只要知道在每个位置上，在这个位置之前最小的数和这个位置之后最大的数，就可以通过差值计算拿到在该位置左右进行买入卖出能拿到的最大利润。

        首先从实现上来说，这样子解这道题肯定是没有问题的，只需要最多进行三次循环：正循环一次，记录到每个位置时能买入的最低值；反着循环一次，记录到每个位置时，在这个位置之后会出现的最大卖出值；再循环一次，计算每个位置上在左边买右边卖能赚到的最大值。简单优化后，可以将三次循环减少为两次：正向扫描一次找到所有位置左边的最小值。反着扫描的时候，在拿到该位置右边的最大值的时候，直接与左边的最小值求差。但即便这样，在此题上消耗的时间最少为2N，空间最少为N（N为数组的长度，空间消耗最小为一个用来存储到每个位置时左边最小值的数组）。

        其实这道题不论从时间还是空间上，都还能有很大的优化空间：

        上面我们已经知道了，买入一定发生在卖出之前，即买入的价格在数组中的序号一定是小于卖出的价格在数组中的序号的。同时，我们希望买入的价尽可能的小，而卖出的价尽可能的高。

        由“买入一定在卖出左边”这里想到，是不是只进行一次循环就可以了。所以可以从数组的第一个数开始向后思考：

        我们用两个变量来记录两个值，一个值是我们到目前为止碰到的最小的数（到目前为止可以买入的最低价），另一个变量用来记录我们到目前为止已经完成买入卖出的话可以赚到的最大值。从第一个数开始向最后循环，每碰到一个数，如果这个数比我们存的最小买入价更小，我们更新最小买入价，这个值可以在之后卖出的时候提供一个更小的买入价。如果当前碰到的价格比现在存的最小买入价要大，我们就计算如果现在卖出可以赚到的数值，然后与我们记录的在之前的最大差值，如果更大的话就更新。这样在扫描了一遍之后，我们记录差值的变量就必然会被更新成为最小买入与最大卖出的差值。python代码实现如下：

第二题，不限制交易次数

        第二题与第一题的区别在于，题目的限制由只能买卖一次变成了可以进行无数次的买卖，但是同时只能有一笔交易在进行中，即只有将之前买的卖出之后，才能进行下一次的买入。

        既然可以进行无数次的交易，那么我们需要考虑的就是“用最少的时间和空间将所有的利润都获取到”。

        因为在第一题中我们已经实现了只扫描一次的算法，所以现在我们仍然在只扫描一次的基础上思考如何拿到所有可以赚到的差值。

        当我们扫描到位置 i 的时候，如果price[i]是大于price[i - 1]的，那么这个差值就可以作为我们赚到的。因为我们不需要考虑交易次数的限制，所以我们一定可以通过通过交易拿到这个差值。如果price[i]小于price[i - 1]那么我们认为在之前的交易已经结束了，我们更新我们的买入价，之后遇到较高的价的时候，与当前的低买入价求差。我们的宗旨是：只要在涨，就赚下差值，只要跌了，就重新开始。因为我们碰到下面这种情况的时候，x1+x2一定是大于x3的，所以一旦我们在扫描的时候发现当前值就变小了，就开始重新算差值。

        具体python实现如下：

第三题，最多交易两次

        第三题的限制是最多进行两次交易，同一时间只能有一笔交易存在。

        因为两笔交易相对独立，因为我们有第一题的基础，所以我们可以将这题进行拆解：找到一个位置，在这个位置左边完成一次交易，右边完成一次交易，得到两次交易的差值之和。

        在第一题中，我们从提一个数开始向后扫描，扫到哪个位置就能得到一直到那个位置我们完成一次交易所能得到的最大差值。所以在此题中可以进行正反两次扫描，分别获得每个位置前面完成一次交易所能得到的最大差值和后面完成一次交易能得到的最大值。然后计算所有位置上两次交易得到的结果，取到最大值，就是此题的答案。

扩展

        通过以上三题，我们可以发现题目中真正限定的其实就是交易的次数。虽然三道题的实现过程都不一样，但是我们是可以将三道题进行一个共同的抽象的：

        给定一个数组表示股票每天的价格，在最多完成 k 次交易的情况下如何获利最多。

        此时，我们就需要换一种思路，找到一个更通用的方法。因为现在k对于我们来说是一个变量，k表示的是最多能完成的交易次数，而不是必须要完成的交易次数。所以交易1~k次的情况我们都需要考虑。

        我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：

    diff = prices[i] - prices[i - 1]

    local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)

    global[i][j] = max(local[i][j], global[i - 1][j])

        我们需要进行两级的循环，分别对应 i 与 j 。这样在完成循环后，global[len(prices)][k]就是我们所要求的值。也即股票买卖的第四题。

        本次只分享到这里，股票买卖的最后两题又加入了新的额外限定条件，如果有兴趣可以尝试解答一下。