算法@LeetCode:BestTimeToBuyAndSell

Log

• 【170420】完成 01 版（Python）提交
• 【170423】研究过参考答案并记录

题目

Best Time to Buy and Sell Stock

【题目类型备注】

数组, 动态规划

提交

01

【语言】

Python

【时间】

170420

【思路】

（是按照「动态规划」的分类来查找题目的，因此直接思考如何用 DP 的思路来解题）

和最大和子序列很像，有下述特征，是典型的 DP 题：

1. 直觉思路就是 O(n^2) 的枚举法
2. 和起止点位置有关
3. 和起止点之间的数据大小有关
4. n 规模的问题可以 n-1 规模的问题为基础，考虑第 n 项的影响，从而得到解

关键是如何实现上述第 4 点。假设 n-1 规模的问题已经有解，那么 n 规模的问题将受到第 n 个元素 prices[n] 下述影响：

1. prices[n] 会影响答案 profit
2. prices[n] 不会影响答案 profit

何时将影响答案，何时不影响呢？显然和 n-1 规模的解中的买入日、卖出日有关（日期隐含了价格信息，而且最后的答案受日期的影响，即卖出日必须在买入日之后。因此除了当前规模的 profit，只要记录日期信息即可）。先大致考虑下，何时不会影响答案：

1. 不卖出：prices[n] 比前一规模的问题中的买入价还低：利润为负，由于「最多可交易 1 次」，也就是可以不交易，因此选择不在今天卖出，会更划算
2. 能卖出：prices[n] 比前一规模的问题中买入价高，但与买入价的差值没有高于当前最高利润，那么显然也不在今天卖出，会更划算

那么何时会影响答案呢？显然，由于第 n 天一定在 n-1 规模问题的买入日之后，所以是可交易的。然后首先需要满足：prices[n] 比前一规模的问题中买入价高。在此前提下：（price_buy_before 为 n-1 规模的问题中的买入价，profit 为 n-1 规模的问题中的利润）

1. 我们至少需要比较 prices[n] - price_buy_before 与 profit 之间的关系
2. 此外， 在第 n 天也可能出现比之前买入价更低的价格，然后在此后某一天出现一个高价，那么在这个更低的价格时买入而不是在前面 n-1 天时就买入，显然会得到更高的回报。考虑下述序列 [5, 3, 7, 6, 2, 8, 1] 即可：在 2 出现之前，显然是在 3 买入即可；当 2 出现时，仍然是 3 买入；但当 8 出现时，解显然变成了 2 买 8 卖。也就是说，实际上要考虑当 prices[n] < price_buy_before 时的情况，额外多记录一个比当前买入价更低的最低买入价 prices_buy_before_morelow，以便在后续出现高价时将买入价修改为那个更低的价格
3. 当第 n 天的价格高于之前的买入价时，只要比较之前的利润 profit 是否低于第 n 天的价格与之前那个更低的买入价之间的差额即可（初始化时对该变量做一些处理即可）
4. 若一直无法卖出（从第一天开始就一直没遇到比首日价格更高的价格），且遇到了比当前「买入价」（即之前较低的一个价格）更低的价格，就将买入价更新为该价格。理由是：反正之前一直没卖出，当找到能卖出价格时，也必定是用这些更低的价格买入，而非用之前更高的价格卖出。

基本思路如上所述。代码见下

【代码】

class Solution(object):
    def maxProfit(self, prices):
        """ 
        :type prices: List[int]
        :rtype: int
        """
    
        if len(prices) < 2:
          return 0
        else:
          lowth  = prices[0:2].index(min(prices[0:2]))
          highth = prices[0:2].index(max(prices[0:2]))
          morelowth = lowth
          profit = prices[highth] - prices[lowth]
          if highth <= lowth:
            profit = 0 
    
          if len(prices) == 2:
            return profit
          else:
            i = 2 
            while (len(prices) != i): 
              if prices[i] <= prices[lowth]:
                if highth <= lowth:
                  lowth = i 
                if prices[i] < prices[morelowth]:
                  morelowth = i 
                i += 1
              else:#prices[i] > prices[lowth]
                if profit < prices[i] - prices[morelowth]:
                  profit = prices[i] - prices[morelowth]
                  highth = i 
                  lowth = morelowth
                 
                i += 1
    +
        return profit

【结果】

运行时：45 ms

报告链接：https://leetcode.com/submissions/detail/100651999/

不知道其他拥有 LeetCode 帐号的人能不能看到该报告，所以顺便附图如下：

Your runtime beats 93.60% of python submissions.

00

参考解法：

• C++

只选用了 C++的参考解法，因为这个解法把该问题和之前的问题联系到了一起，非常有意思也非常巧妙。该解法特别提到了 Kadane 算法。仔细一想，当转换一下这题的表述，真的就和最大子序列问题是一样的。为什么这么说？只需要一个小小的代数表示即可：

令 prices[k] = x_k，那么数列 [x_1 - x_0, x_2 - x_1, ..., x_n - x_n_1]（x_n_1 表示 prices[n-1]） 中，任意在下标 i 与 k 处截断为 [x_i - x_i_1, ..., x_k - x_k_1] 后，这个子数列的和就是：第 i 天买入、第 k 天卖出的价格（为什么这么说？因为：x[i] - x[i-1] + x[i+1] - x[i] + ... + x[k] - x[k-1] = x[k] - x[i]）。于是只要我们将这个题目稍微一转换，就可以完全套用最大子数列和的解法……

自己实现一遍最优解：

• [language]。。。