Best Time to Buy and Sell Stock IV

Question

  1. Say you have an array for
  2. which the ith element is the price of a given stock on day i.
  4. Design an algorithm to find the maximum profit.
  5. You may complete at most k transactions.
  7. Example
  8. Given prices = [4,4,6,1,1,4,2,5], and k = 2, return 6.
  10. Note
  11. You may not engage in multiple transactions at the same time
  12. (i.e., you must sell the stock before you buy again).
  14. Challenge
  15. O(nk) time.

题解1

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

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

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

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

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

Python

  1. class Solution:
  2.     """
  3.     @param k: an integer
  4.     @param prices: a list of integer
  5.     @return: an integer which is maximum profit
  6.     """
  7.     def maxProfit(self, k, prices):
  8.         if prices is None or len(prices) <= 1 or k <= 0:
  9.             return 0
  11.         n = len(prices)
  12.         # k >= prices.length / 2 ==> multiple transactions Stock II
  13.         if k >= n / 2:
  14.             profit_max = 0
  15.             for i in xrange(1, n):
  16.                 diff = prices[i] - prices[i - 1]
  17.                 if diff > 0:
  18.                     profit_max += diff
  19.             return profit_max
  21.         f = [[0 for i in xrange(k + 1)] for j in xrange(n + 1)]
  22.         for j in xrange(1, k + 1):
  23.             for i in xrange(1, n + 1):
  24.                 for x in xrange(0, i + 1):
  25.                     f[i][j] = max(f[i][j], f[x][j - 1] + self.profit(prices, x + 1, i))
  27.         return f[n][k]
  29.     # calculate the profit of prices(l, u)
  30.     def profit(self, prices, l, u):
  31.         if l >= u:
  32.             return 0
  33.         valley = 2**31 - 1
  34.         profit_max = 0
  35.         for price in prices[l - 1:u]:
  36.             profit_max = max(profit_max, price - valley)
  37.             valley = min(valley, price)
  38.         return profit_max

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param k: An integer
  5.      * @param prices: Given an integer array
  6.      * @return: Maximum profit
  7.      */
  8.     int maxProfit(int k, vector<int> &prices) {
  9.         if (prices.size() <= 1 || k <= 0) return 0;
  11.         int n = prices.size();
  12.         // k >= prices.length / 2 ==> multiple transactions Stock II
  13.         if (k >= n / 2) {
  14.             int profit_max = 0;
  15.             for (int i = 1; i < n; ++i) {
  16.                 int diff = prices[i] - prices[i - 1];
  17.                 if (diff > 0) {
  18.                     profit_max += diff;
  19.                 }
  20.             }
  21.             return profit_max;
  22.         }
  24.         vector<vector<int> > f = vector<vector<int> >(n + 1, vector<int>(k + 1, 0));
  25.         for (int j = 1; j <= k; ++j) {
  26.             for (int i = 1; i <= n; ++i) {
  27.                 for (int x = 0; x <= i; ++x) {
  28.                     f[i][j] = max(f[i][j], f[x][j - 1] + profit(prices, x + 1, i));
  29.                 }
  30.             }
  31.         }
  33.         return f[n][k];
  34.     }
  36. private:
  37.     int profit(vector<int> &prices, int l, int u) {
  38.         if (l >= u) return 0;
  40.         int valley = INT_MAX;
  41.         int profit_max = 0;
  42.         for (int i = l - 1; i < u; ++i) {
  43.             profit_max = max(profit_max, prices[i] - valley);
  44.             valley = min(valley, prices[i]);
  45.         }
  47.         return profit_max;
  48.     }
  49. };

Java

  1. class Solution {
  2.     /**
  3.      * @param k: An integer
  4.      * @param prices: Given an integer array
  5.      * @return: Maximum profit
  6.      */
  7.     public int maxProfit(int k, int[] prices) {
  8.         if (prices == null || prices.length <= 1 || k <= 0) return 0;
  10.         int n = prices.length;
  11.         if (k >= n / 2) {
  12.             int profit_max = 0;
  13.             for (int i = 1; i < n; i++) {
  14.                 if (prices[i] - prices[i - 1] > 0) {
  15.                     profit_max += prices[i] - prices[i - 1];
  16.                 }
  17.             }
  18.             return profit_max;
  19.         }
  21.         int[][] f = new int[n + 1][k + 1];
  22.         for (int j = 1; j <= k; j++) {
  23.             for (int i = 1; i <= n; i++) {
  24.                 for (int x = 0; x <= i; x++) {
  25.                     f[i][j] = Math.max(f[i][j], f[x][j - 1] + profit(prices, x + 1, i));
  26.                 }
  27.             }
  28.         }
  30.         return f[n][k];
  31.     }
  33.     private int profit(int[] prices, int l, int u) {
  34.         if (l >= u) return 0;
  36.         int valley = Integer.MAX_VALUE;
  37.         int profit_max = 0;
  38.         for (int i = l - 1; i < u; i++) {
  39.             profit_max = Math.max(profit_max, prices[i] - valley);
  40.             valley = Math.min(valley, prices[i]);
  41.         }
  42.         return profit_max;
  43.     }
  44. };

源码分析

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

复杂度分析

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

Reference