{"id":8901,"date":"2021-11-28T20:24:27","date_gmt":"2021-11-29T04:24:27","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8901"},"modified":"2021-11-28T20:29:19","modified_gmt":"2021-11-29T04:29:19","slug":"leetcode-188-best-time-to-buy-and-sell-stock-iv","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-188-best-time-to-buy-and-sell-stock-iv\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 188. Best Time to Buy and Sell Stock IV"},"content":{"rendered":"\n<p>You are given an integer array&nbsp;<code>prices<\/code>&nbsp;where&nbsp;<code>prices[i]<\/code>&nbsp;is the price of a given stock on the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;day, and an integer&nbsp;<code>k<\/code>.<\/p>\n\n\n\n<p>Find the maximum profit you can achieve. You may complete at most&nbsp;<code>k<\/code>&nbsp;transactions.<\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> k = 2, prices = [2,4,1]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> k = 2, prices = [3,2,6,5,0,3]\n<strong>Output:<\/strong> 7\n<strong>Explanation:<\/strong> 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.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>0 &lt;= k &lt;= 100<\/code><\/li><li><code>0 &lt;= prices.length &lt;= 1000<\/code><\/li><li><code>0 &lt;= prices[i] &lt;= 1000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>profit[i][j] := max profit by making <span class=\"has-inline-color has-vivid-red-color\"><strong><span style=\"text-decoration: underline;\">up to j sells<\/span><\/strong><\/span> in first i days. (Do not hold any share)<br>balance[i][j] := max balance by making at to <span class=\"has-inline-color has-vivid-red-color\"><strong><span style=\"text-decoration: underline;\">up j buys<\/span><\/strong><\/span> in first i days. (Most hold a share)<\/p>\n\n\n\n<p>balance[i][j] = max(balance[i-1][j], profit[i-1][<span class=\"has-inline-color has-vivid-red-color\"><strong>j-1<\/strong><\/span>] &#8211; prices[i]) \/\/ do nothing or buy at i-th day.<br>profit[i][j] = max(profit[i-1][j], balance[i-1][<span class=\"has-inline-color has-vivid-red-color\"><strong>j<\/strong><\/span>] + prices[i]) \/\/ do nothing or sell at i-th day.<\/p>\n\n\n\n<p>ans = profit[n-1][k]<\/p>\n\n\n\n<p>Time complexity: O(n*k)<br>Space complexity: O(k)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxProfit(int k, vector<int>& prices) {\n    const int n = prices.size();     \n    vector<int> balance(k + 1, INT_MIN);\n    vector<int> profit(k + 1, 0);    \n    for (int i = 0; i < n; ++i)\n      for (int j = 1; j <= k; ++j) {\n        balance[j] = max(balance[j], profit[j - 1] - prices[i]);\n        profit[j] = max(profit[j], balance[j] + prices[i]);\n      }\n    return profit[k];\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Related Problems<\/strong><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-121-best-time-to-buy-and-sell-stock\/\" data-type=\"post\" data-id=\"1319\">\u82b1\u82b1\u9171 LeetCode 121. Best Time to Buy and Sell Stock<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-122-best-time-to-buy-and-sell-stock-ii\/\" data-type=\"post\" data-id=\"5735\">\u82b1\u82b1\u9171 LeetCode 122. Best Time to Buy and Sell Stock II<\/a><\/li><li><a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-309-best-time-to-buy-and-sell-stock-with-cooldown\/\" data-type=\"post\" data-id=\"1517\">\u82b1\u82b1\u9171 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown<\/a><\/li><\/ul>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;prices&nbsp;where&nbsp;prices[i]&nbsp;is the price of a given stock on the&nbsp;ith&nbsp;day, and an integer&nbsp;k. Find the maximum profit you can achieve. You&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,206],"class_list":["post-8901","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-stock","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8901","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8901"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8901\/revisions"}],"predecessor-version":[{"id":8904,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8901\/revisions\/8904"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8901"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8901"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8901"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}