Welcome to Subscribe On Youtube

Question

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

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

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

 

Example 1:

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

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
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.

 

Constraints:

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

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
• C++
• Python
• Go
• C#

• 
  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];
          }
      }
  }
  
  ############
  
  class Solution {
      public int maxProfit(int k, int[] prices) {
          int n = prices.length;
          if (n <= 1) {
              return 0;
          }
          int[][][] dp = new int[n][k + 1][2];
          for (int i = 1; i <= k; ++i) {
              dp[0][i][1] = -prices[0];
          }
          for (int i = 1; i < n; ++i) {
              for (int j = 1; j <= k; ++j) {
                  dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]);
                  dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1]);
              }
          }
          return dp[n - 1][k][0];
      }
  }
  

• // 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];
      }
  };
  

• class Solution:
      def maxProfit(self, k: int, prices: List[int]) -> int:
          n = len(prices)
          if n < 2:
              return 0
          # 3-D dp: n days * k completed transactions * 2 ops buy/sell
          # my understanding, one transaction, meaning both buy then sell completed
          dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]
          for i in range(1, k + 1):
              dp[0][i][1] = -prices[0] # dp[][][ 0/1 ], 1 is buy, 0 is sell
          for i in range(1, n):
              for j in range(1, k + 1):
                  dp[i][j][0] = max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]) # [1] => sell happening <= that day
                  dp[i][j][1] = max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1])
          return dp[-1][k][0]
  
  class Solution:
      def maxProfit(self, k: int, prices: List[int]) -> int:
          @cache
          def dfs(i, j, k):
              if i >= len(prices):
                  return 0
              ans = dfs(i + 1, j, k)
              if k:
                  ans = max(ans, prices[i] + dfs(i + 1, j, 0))
              elif j:
                  ans = max(ans, -prices[i] + dfs(i + 1, j - 1, 1))
              return ans
  
          return dfs(0, k, 0)
  
  ##############
  
  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])
  
  

• func maxProfit(k int, prices []int) int {
  	n := len(prices)
  	if n < 2 {
  		return 0
  	}
  	dp := make([][][]int, n)
  	for i := 0; i < n; i++ {
  		dp[i] = make([][]int, k+1)
  		for j := 0; j <= k; j++ {
  			dp[i][j] = make([]int, 2)
  		}
  	}
  	for i := 1; i <= k; i++ {
  		dp[0][i][1] = -prices[0]
  	}
  	for i := 1; i < n; i++ {
  		for j := 1; j <= k; j++ {
  			dp[i][j][0] = max(dp[i-1][j][1]+prices[i], dp[i-1][j][0])
  			dp[i][j][1] = max(dp[i-1][j-1][0]-prices[i], dp[i-1][j][1])
  		}
  	}
  	return dp[n-1][k][0]
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• using System;
  using System.Collections.Generic;
  using System.Linq;
  
  public class Comparer : IComparer<LinkedListNode<Tuple<int, int>>>
  {
      public int Compare(LinkedListNode<Tuple<int, int>> left, LinkedListNode<Tuple<int, int>> right)
      {
          var result = left.Value.Item1.CompareTo(right.Value.Item1);
          if (result == 0 && left != right)
          {
              return left.Value.Item2.CompareTo(right.Value.Item2);
          }
          return result;
      }
  }
  
  public class Solution {
      private SortedSet<LinkedListNode<Tuple<int, int>>> heap = new SortedSet<LinkedListNode<Tuple<int, int>>>(new Comparer());
      private LinkedList<Tuple<int, int>> list = new LinkedList<Tuple<int, int>>();
      
      private int lable = 0;
      private Tuple<int, int> CreateNodeValue(int value)
      {
          return Tuple.Create(value, lable++);
      }
      
      public int MaxProfitStupid(int k, int[] prices)
      {
          var f = new int[prices.Length + 1, k + 1];
          for (var i = 2; i <= prices.Length; ++i)
          {
              for (var kk = 1; kk <= k; ++kk)
              {
                  for (var j = 0; j + 1 < i; ++j)
                  {
                      f[i, kk] = Math.Max(f[i, kk], Math.Max(Math.Max(f[i, kk - 1], f[i - 1, kk]), f[j, kk - 1] + prices[i - 1] - prices[j]));
                  }
              }
          }
          return f[prices.Length, k];
      }
      
      public int MaxProfit(int k, int[] prices) {
          var result = 0;
          var i = 0;
          var profitCount = 0;
          var tempList = new List<Tuple<int, bool>>();
          while (i + 1 < prices.Length)
          {
              var highIndex = i;
              while (i + 1 < prices.Length && prices[i] >= prices[i + 1])
              {
                  ++i;
              }
              var lowIndex = i;
              while (i + 1 < prices.Length && prices[i] <= prices[i + 1])
              {
                  ++i;
              }
              var highIndex2 = i;
              
              if (highIndex != lowIndex)
              {
                  tempList.Add(Tuple.Create(prices[highIndex] - prices[lowIndex], false));
              }
              if (lowIndex != highIndex2)
              {
                  tempList.Add(Tuple.Create(prices[highIndex2] - prices[lowIndex], true));
                  result += prices[highIndex2] - prices[lowIndex];
                  ++profitCount;
              }
          }
          
          // Trim gaps
          if (tempList.Any() && tempList.First().Item2 == false)
          {
              tempList.RemoveAt(0);
          }
          if (tempList.Any() && tempList.Last().Item2 == false)
          {
              tempList.RemoveAt(tempList.Count - 1);
          }
          
          foreach (var temp in tempList)
          {
              var node = list.AddLast(CreateNodeValue(temp.Item1));
              heap.Add(node);
          }
          //Console.WriteLine("profitCount: {0}. tempList size: {1}. Heap size: {2}.", profitCount, tempList.Count, heap.Sum(item =>item.Value.Count));
                  
          for (var j = 0; j < profitCount - k; ++j)
          {
              var node = heap.Min;
              result -= node.Value.Item1;
              //Console.WriteLine(node.Value);
              var previous = node.Previous;
              var next = node.Next;
              var newValue = (previous == null ? 0 : previous.Value.Item1) + (next == null ? 0 : next.Value.Item1) - node.Value.Item1;
              if (previous != null)
              {
                  heap.Remove(previous);
                  list.Remove(previous);
              }
              if (next != null)
              {
                  heap.Remove(next);
                  list.Remove(next);
              }
              if (previous != null && next != null)
              { 
                  var newNode = list.AddBefore(node, CreateNodeValue(newValue));
                  heap.Add(newNode);
              }
              heap.Remove(node);
              list.Remove(node);
          }
  
          return result;
      }
  } 
  

All Problems

All Solutions