Best Time to Buy and Sell Stock IV

Question

Say you have an array for
which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit.
You may complete at most k transactions.

Example
Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.

Note
You may not engage in multiple transactions at the same time
(i.e., you must sell the stock before you buy again).

Challenge
O(nk) time.

题解1

卖股票系列中最难的一道，较易实现的方法为使用动态规划，动规的实现又分为大约3大类方法，这里先介绍一种最为朴素的方法，过不了大量数据，会 TLE.

最多允许 k 次交易，由于一次增加收益的交易至少需要两天，故当 k >= n/2时，此题退化为卖股票的第二道题，即允许任意多次交易。当 k < n/2 时，使用动规来求解，动规的几个要素如下：

f[i][j] 代表第 i 天为止交易 k 次获得的最大收益，那么将问题分解为前 x 天交易 k-1 次，第 x+1 天至第 i 天交易一次两个子问题，于是动态方程如下：

f[i][j] = max(f[x][j - 1] + profit(x + 1, i))

简便起见，初始化二维矩阵为0，下标尽可能从1开始，便于理解。

Python

class Solution:
    """
    @param k: an integer
    @param prices: a list of integer
    @return: an integer which is maximum profit
    """
    def maxProfit(self, k, prices):
        if prices is None or len(prices) <= 1 or k <= 0:
            return 0

        n = len(prices)
        # k >= prices.length / 2 ==> multiple transactions Stock II
        if k >= n / 2:
            profit_max = 0
            for i in xrange(1, n):
                diff = prices[i] - prices[i - 1]
                if diff > 0:
                    profit_max += diff
            return profit_max

        f = [[0 for i in xrange(k + 1)] for j in xrange(n + 1)]
        for j in xrange(1, k + 1):
            for i in xrange(1, n + 1):
                for x in xrange(0, i + 1):
                    f[i][j] = max(f[i][j], f[x][j - 1] + self.profit(prices, x + 1, i))

        return f[n][k]

    # calculate the profit of prices(l, u)
    def profit(self, prices, l, u):
        if l >= u:
            return 0
        valley = 2**31 - 1
        profit_max = 0
        for price in prices[l - 1:u]:
            profit_max = max(profit_max, price - valley)
            valley = min(valley, price)
        return profit_max

源码分析

注意 Python 中的多维数组初始化方式，不可简单使用[[0] * k] * n], 具体原因是因为 Python 中的对象引用方式。可以优化的地方是 profit 方法及最内存循环。

复杂度分析

三重循环，时间复杂度近似为 $$O(n^2 \cdot k)$$, 使用了 f 二维数组，空间复杂度为 $$O(n \cdot k)$$.

Reference

  • [LeetCode]Best Time to Buy and Sell Stock IV | 书影博客

    class Solution:
  # @return an integer as the maximum profit 
  def maxProfit(self, k, prices):
      size = len(prices)
      if k > size / 2:
          return self.quickSolve(size, prices)
      dp = [None] * (2 * k + 1)
      dp[0] = 0
      for i in range(size):
          for j in range(min(2 * k, i + 1) , 0 , -1):
              dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
      return max(dp)

  def quickSolve(self, size, prices):
      sum = 0
      for x in range(size - 1):
          if prices[x + 1] > prices[x]:
              sum += prices[x + 1] - prices[x]
      return sum

results matching ""

    No results matching ""