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
-
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; } }