{"id":8930,"date":"2021-11-28T23:26:38","date_gmt":"2021-11-29T07:26:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8930"},"modified":"2021-11-28T23:27:17","modified_gmt":"2021-11-29T07:27:17","slug":"leetcode-123-best-time-to-buy-and-sell-stock-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-123-best-time-to-buy-and-sell-stock-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 123. Best Time to Buy and Sell Stock III"},"content":{"rendered":"\n<p>You are given an 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.<\/p>\n\n\n\n<p>Find the maximum profit you can achieve. You may complete&nbsp;<strong>at most two transactions<\/strong>.<\/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> prices = [3,3,5,0,0,3,1,4]\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.\nThen buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.<\/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> prices = [1,2,3,4,5]\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.\nNote that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> prices = [7,6,4,3,1]\n<strong>Output:<\/strong> 0\n<strong>Explanation:<\/strong> In this case, no transaction is done, i.e. max profit = 0.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> prices = [1]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= prices.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>0 &lt;= prices[i] &lt;= 10<sup>5<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>A special case of <a href=\"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-188-best-time-to-buy-and-sell-stock-iv\/\" data-type=\"post\" data-id=\"8901\">\u82b1\u82b1\u9171 LeetCode 188. Best Time to Buy and Sell Stock IV<\/a> where k = 2.<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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(vector<int>& prices) {\n    constexpr int k = 2;\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<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;prices&nbsp;where&nbsp;prices[i]&nbsp;is the price of a given stock on the&nbsp;ith&nbsp;day. Find the maximum profit you can achieve. You may complete&nbsp;at most two&#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,217,206],"class_list":["post-8930","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-hard","tag-stock","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8930","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=8930"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8930\/revisions"}],"predecessor-version":[{"id":8932,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8930\/revisions\/8932"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}