{"id":5735,"date":"2019-10-09T20:51:00","date_gmt":"2019-10-10T03:51:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5735"},"modified":"2019-10-09T20:51:11","modified_gmt":"2019-10-10T03:51:11","slug":"leetcode-122-best-time-to-buy-and-sell-stock-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-122-best-time-to-buy-and-sell-stock-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 122. Best Time to Buy and Sell Stock II"},"content":{"rendered":"\n<p>Say you have an array for which the&nbsp;<em>i<\/em><sup>th<\/sup>&nbsp;element is the price of a given stock on day&nbsp;<em>i<\/em>.<\/p>\n\n\n\n<p>Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).<\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;You may not engage in multiple transactions at the same time (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> [7,1,5,3,6,4]\n<strong>Output:<\/strong> 7\n<strong>Explanation:<\/strong> Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.\n&nbsp;            Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.\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> [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.\n&nbsp;            Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are\n&nbsp;            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> [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.<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\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    int profit = 0;\n    for (size_t i = 1; i < prices.size(); ++i)        \n      profit += max(0, prices[i] - prices[i - 1]);\n    return profit;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Say you have an array for which the&nbsp;ith&nbsp;element is the price of a given stock on day&nbsp;i. Design an algorithm to find the maximum profit.&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[20,222,88],"class_list":["post-5735","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-array","tag-easy","tag-greedy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5735","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=5735"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5735\/revisions"}],"predecessor-version":[{"id":5737,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5735\/revisions\/5737"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5735"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5735"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5735"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}