Maximum product subarray (Question number 152)

The title

Given an array of integers, nums, find the contiguous subarray with the largest product (that contains at least one number) and return the corresponding product.

Example 1:

Input: [2,3,-2,4] output: 6 description: subarray [2,3] has maximum product 6.Copy the code

Example 2:

Input: [- 2, 0, 1] output: 0 explanation: the result can't to 2, because [2, 1] is not an array.Copy the code

link

Leetcode-cn.com/problems/ma…

explain

This question really can’t think of the answer, do not know is the mathematics base is too poor or the brain is not enough to use, did not think of this solution, completely without any idea ah.

Logic are simple, only need one variable to record the maximum product, the product of a variable to record, the smallest value of each cycle time need four variables, the maximum value multiplied by the current first number, to give the minimum value multiplied in the current digital, finally take the current Numbers and twice the product of the maximum and the minimum and assign a value to the Max and min.

It may not be clear, but look at the code.

Your own answer

There is no

A better way

var maxProduct = function(nums) {
  var res = nums[0]
      max = res
      min = res
      tmp1 = 0
      tmp2 = 0
  for (let i = 1; i < nums.length; i++) {
    tmp1 = max * nums[i]    
    tmp2 = min * nums[i]
    max = Math.max(tmp1, tmp2, nums[i])
    min = Math.min(tmp1, tmp2, nums[i])
    res = Math.max(max, res)
  }
  return res
};
Copy the code

See, it’s very simple, but I didn’t understand the equation of dynamic programming and I got confused.

The best time to buy and sell stocks (Question 121)

The title

Given an array prices, the i-th element prices[I] represents the i-th day price of a given stock.

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), 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 greater than the buying price; Also, you can't sell before you buy.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

link

Leetcode-cn.com/problems/be…

explain

This problem should be solved step by step according to the steps of dynamic programming, but I didn’t think of the specific steps during this period, and came up with the answer directly. In fact, I should follow the steps step by step, so as to exercise the disassembly ability in complex situations.

In this case, you need two variables to store the state, which is memorization.

The first variable is called min, which is the minimum value, and it’s assigned to the first value in the array, and as you go through the array you’re going to compare each time, to see if the current element is smaller or if min is smaller, and you’re going to take the smaller one and assign it to min.

The second variable is called RES, which is the final result, and every time you go through it, the difference between the current element and the current element minus min is compared to the current res, and you take the larger value. The initial value of res is zero, which is what they say, which also means that the array is sorted from large to small.

Your own answer

var maxProfit = function(prices) {
  var min = prices[0]
      res = 0
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i])
    res = Math.max(prices[i] - min, res)
  }
  return res
};
Copy the code

Simple and clear, not too much to say.

A better way

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ