Question

Formatted question description: https://leetcode.ca/all/188.html

 188 Best Time to Buy and Sell Stock IV

 Say you have an array for which the i-th 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.

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

 Example 1:

 Input: [2,4,1], k = 2
 Output: 2
 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

 Example 2:

 Input: [3,2,6,5,0,3], k = 2
 Output: 7
 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
 Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 @tag-array

Algorithm

Extend from problem-123.

Define local[i][j] as the maximum profit that can be made at most j transactions on the i-th day and the last transaction sold on the last day, which is the local optimal.

Then we define global[i][j] as the maximum profit that can be performed at most j transactions when the i-th day is reached, which is the global optimal (not neccessarily last transaction sold on the last day). Their recurrence is:

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])

The local optimal value is compared to the global optimal one less traded the previous day plus a difference greater than 0, and the local optimal of the previous day plus the difference, whichever is greater, and the global optimal compares the local optimal And the previous day’s global optimal.

Code

Java

  • 
    public class Best_Time_to_Buy_and_Sell_Stock_IV {
    
        class Solution {
            public int maxProfit(int k, int[] prices) {
    
                int n = prices.length;
                if (n <= 1) {
                    return 0;
                }
    
                int[][] g = new int[n][k + 1];
                int[][] l = new int[n][k + 1];
    
                for (int i = 1; i < prices.length; ++i) {
                    int diff = prices[i] - prices[i - 1];
                    for (int j = 1; j <= k; ++j) {
                        // 最后一天卖出, 因为已经j次交易,j次的买入已经完成 => l[i - 1][j] + diff
                        l[i][j] = Math.max(g[i - 1][j - 1] + Math.max(diff, 0), l[i - 1][j] + diff);
                        g[i][j] = Math.max(l[i][j], g[i - 1][j]); // 第j天有没有卖出,两种情况
                    }
                }
    
                return g[n - 1][k];
            }
        }
    
        class Solution_1D {
            public int maxProfit(int k, int[] prices) {
    
                int n = prices.length;
                if (n <= 1) {
                    return 0;
                }
    
                //if k >= n/2, then you can make maximum number of transactions.
                // same as in Best_Time_to_Buy_and_Sell_Stock_II
                if (k >= n / 2) {
                    int maxPro = 0;
                    for (int i = 1; i < n; i++) {
                        if (prices[i] > prices[i - 1])
                            maxPro += prices[i] - prices[i - 1];
                    }
                    return maxPro;
                }
    
                int[] global = new int[k + 1];
                int[] local = new int[k + 1]; // k=0, no transaction, profit=0
                for (int i = 0; i < prices.length - 1; i++) {
                    int diff = prices[i + 1] - prices[i];
                    for (int j = k; j >= 1; --j) {
                        local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
                        global[j] = Math.max(global[j], local[j]);
                    }
                }
    
                return global[k];
    
                /**
                 * dp[i, j] represents the max profit up until prices[j] using at most i transactions.
                 *
                 * ### { jj in range of [0, j-1] }
                 * dp[i, j] = max(dp[i, j-1], prices[j] - prices[jj] + dp[i-1, jj])
                 *          = max(dp[i, j-1], prices[j] + max(dp[i-1, jj] - prices[jj]))
                 *
                 * dp[0, j] = 0; 0 transactions makes 0 profit
                 * dp[i, 0] = 0; if there is only one price data point you can't make any transaction.
                 */
    
    //            // @note: below also working
    //            // dp[i, j]: max profit up until prices[j] using at most i transactions.
    //            //           i => transaction
    //            //           j => price day
    //            int[][] dp = new int[k + 1][n];
    //            for (int i = 1; i <= k; i++) { // i=0, no transaction, profit=0
    //                int localMax = dp[i - 1][0] - prices[0]; // 在第一天买
    //                for (int j = 1; j < n; j++) {
    //                    dp[i][j] = Math.max(dp[i][j - 1], prices[j] + localMax);
    //                    localMax = Math.max(localMax, dp[i - 1][j] - prices[j]);
    //                }
    //            }
    //
    //            return dp[k][n - 1];
    
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
    // Time: O(KN^2)
    // Space: O(KN)
    // NOTE: this will get TLE
    class Solution {
    public:
        int maxProfit(int K, vector<int>& A) {
            if (A.empty()) return 0;
            int N = A.size();
            K = min(K, N / 2);
            vector<vector<int>> dp(K + 1, vector<int>(N + 1));
            for (int k = 1; k <= K; ++k) {
                for (int i = 1; i < N; ++i) {
                    int maxVal = INT_MIN;
                    for (int j = 0; j < i; ++j) maxVal = max(maxVal, dp[k - 1][j] - A[j]);
                    dp[k][i + 1] = max(dp[k][i], A[i] + maxVal);
                }
            }
            return dp[K][N];
        }
    };
    
  • import heapq
    import random
    
    
    class Solution(object):
      def findKthLargest(self, nums, k):
        """
        :type A: List[int]
        :type k: int
        :rtype: int
        """
    
        def quickselect(start, end, nums, k):
          if start == end:
            return nums[start]
    
          mid = partition(start, end, nums)
    
          if mid == k:
            return nums[mid]
          elif k > mid:
            return quickselect(mid + 1, end, nums, k)
          else:
            return quickselect(start, mid - 1, nums, k)
    
        def partition(start, end, nums):
          p = random.randrange(start, end + 1)
          pv = nums[p]
          nums[end], nums[p] = nums[p], nums[end]
          mid = start
          for i in range(start, end):
            if nums[i] >= pv:
              nums[i], nums[mid] = nums[mid], nums[i]
              mid += 1
          nums[mid], nums[end] = nums[end], nums[mid]
          return mid
    
        return quickselect(0, len(nums) - 1, nums, k - 1)
    
      def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
          return 0
        stack = []
        heap = []
        v = p = 0
        n = len(prices)
        ans = 0
        while p < n:
          v = p
          while v < n - 1 and prices[v] >= prices[v + 1]:
            v += 1
          p = v + 1
          while p < n and prices[p] > prices[p - 1]:
            p += 1
          while stack and prices[stack[-1][0]] > prices[v]:
            _v, _p = stack.pop()
            heap.append(prices[_p - 1] - prices[_v])
          while stack and prices[stack[-1][1] - 1] < prices[p - 1]:
            heap.append(prices[stack[-1][1] - 1] - prices[v])
            v, _ = stack.pop()
          stack.append((v, p))
    
        heap += [prices[p - 1] - prices[v] for v, p in stack]
        if len(heap) < k:
          return sum(heap)
        self.findKthLargest(heap, k)
        return sum(heap[:k])
    
    

All Problems

All Solutions