After this topic may give up completely brush the topic, on a whim, also a dull. Habits can’t be formed eventually, and it’s hard to get out of a distinctive way without learning the way that suits you. The next step is to spend time figuring out what you can learn, what you can produce, and what you can stick to. This time, is undoubtedly a failure, to look at the Copy city lion’s last question – the best time to buy and sell stocks.

Topic describes

classification difficulty 👍 👎
algorithm Simple (56.09%) 1504 –
The label

An array of ｜
Dynamic programming

The company

amazon | bloomberg | facebook | microsoft | uber

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Tip:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Thought analysis

There are two key points of feeling:

  • One is to find the maximum profit, which is the largest difference between the two values in the array
  • Second, it is necessary to judge that the selling price is larger than the buying price, that is, the latter value is larger than the previous value.

Copy city lion’s old routine – violent solution to go!

AC code

Violent solution

/** @lc app=leetcode.cn id=121 lang=javascript ** [121] Prices */ / @lc code=start /** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { let maxProfit = 0; for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1; j < prices.length; j++) { let profit = prices[j] - prices[i]; if (profit > maxProfit) { maxProfit = profit; } } } return maxProfit; }; // @lc code=endCopy the code

The test seemed to be fine, and when I submitted it confidently, I was blindsided. Boom! Blast! Blast!

Time Limit Exceeded 205/210 cases passed (N/A) Testcase [681331387940850305433389137,57,294,301,491,64,251,498,487,680,621,578,646,591,715,907,923,705,123,467,578,455,3 35607773521966,86,344,664,515,362,709,920,595,43,364,498,117,353,517,824,750,857,112,350,466,399,181,699,385,474,361 , 678,82,50,424,971,286,170,700,889,940,392,713,542,603,351,899,726,562,668,637,259,944,497,445,435,777,263,846,662,947,9 95798384300378728251,99,70,756,612,979,195,382,825,18,139,218,820,404,513,182,238,646,597,498,119,257,200,894,562, 982403803663370120,87,818,103,568,965,516,32,103,857,504,638,576,855,659,324,463,833,688,461,690,403,672,439,250,66 9840751282411163603807556202297,94,895,392,640,548,494,861,365,156,912,657,246,949,380,811,386,172,157,83,143, 695845453594,96,395,255,31,558,143,719,3,634,633,663,491,106,384,778,727,385,143,231,212,229,284,40,188,879,111,26,40 1513435278546,38,866,600,957,411,268,52,935,212,563,524,844,248,206,913,684,226,208,983,292,855,141,266,61,896,604,2 08498372364534231300669690336854344200223829506122898424235672627256834,60,354,263,602,668,66,356 , 91]........................  Expected Answer 999Copy the code

When the size of the array is too large, the memory should be exhausted, similar to Chrome stuck.

How to do? Take a look at community solutions and try what the big boys call dynamic programming.

Dynamic programming of the unknown

From a line of code skillfully use reduce to achieve dynamic programming

The reduce of array in JavaScript is naturally capable of solving dynamic programming equations, so this paper will not do in-depth research for the time being.

/** @lc app=leetcode.cn id=121 lang=javascript ** [121] Prices */ / @lc code=start /** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { return prices.reduce( (p, v) => [Math.min(p[0], v), Math.max(p[1], v - p[0])], [Number.MAX_SAFE_INTEGER, 0] )[1]; }; // @lc code=end // 210/210 cases passed (188 ms) // Your runtime beats 15.5% of javascript submissions // Your memory Each node in the linked list is linked to the linked node.Copy the code

conclusion

Another concept worth in-depth, also do not know what good method can grasp these concepts and ideas to solve problems as soon as possible, confused……

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign