This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

99. Best Time to Buy and sell stocks IV (Best-time-to-buy-and-sell-stock-IV)

The label

  • Transformation of thinking
  • difficult

The title

Leetcode portal

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

Design an algorithm to calculate the maximum profit you can make. You can do k transactions at most.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Input: k = 2, prices = [3,2,6,5,0,3] Output: 7 Then, by buying on day 5 (stock price = 0) and selling on day 6 (stock price = 3), the exchange makes a profit = 3-0 = 3.Copy the code

The basic idea

The difference in this problem is that they fixed 2 transactions, and this time they passed in k

Last time we had 2 points and 2 selling points, so this time we have k points and k selling points

So we can set up two arrays to replace each of the maximum gains of the day

  • [buy1, buy2, buy3….buyk]
  • [cell1, cell2, cell3….cellk]

And then you can do almost the same thing with the state transition. How to transfer? Make sure you get the most out of each day.

State transition equation:

buy[j] = Math.max(buy[j], sell[j-1] - prices[i])
sell[j] = Math.max(sell[j], buy[j] + prices[i])
Copy the code

Writing implement

var maxProfit = function(k, prices) {
  // If k is more than half, it is also invalid
  k = Math.min(k, Math.floor(prices.length / 2))

  let buy = new Array(k+1).fill(-Infinity)
  let sell = new Array(k+1).fill(0)

  for (let i = 0; i < prices.length; i++) {
    for (let j = 1; j < k+1; j++) {
      buy[j] = Math.max(buy[j], sell[j-1] - prices[i])
      sell[j] = Math.max(sell[j], buy[j] + prices[i])
    }
  }
  return sell.pop()
};

let k = 2, prices = [3.2.6.5.0.3]
console.log(maxProfit(k, prices))
Copy the code

100. Best time to buy or sell stocks includes best-time-to-buy-and-sell-stock-with-cooldown.

The label

  • Transformation of thinking
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

Given an array of integers, the ith element represents the stock price on the ith day.

Design an algorithm to calculate the maximum profit. You can make as many trades (buying and selling a stock multiple times) as you can with the following constraints:

  • You can’t participate in more than one transaction at a time (you have to sell your previous shares before buying again).
  • After selling, you cannot buy the stock the next day (i.e. freeze period is 1 day).
Input: [1,2,3,0,2] output: 3 explanation: the corresponding trading states are: [buy, sell, freeze period, buy, sell]Copy the code

The basic idea

Because of the freezing period, at the end of any given day we are in one of three states:

  • If you don’t have it, you can buy it
  • You can sell it
  • I can’t buy it if I don’t have it

Our goal is to maximize returns. Similar to the previous problem, we record the current maximum profit as buy sell sellPre buy is the best state to buy, sell is the best state to sell, and sellPre is the previous state to sell.

Writing implement

var maxProfit = function(prices) {
  let [buy, sell, sellPre] = [-Infinity.0.0]
  for (let i = 0; i < prices.length; i++) {
    buy = Math.max(buy, sellPre - prices[i])
    sellPre = sell
    sell = Math.max(sell, buy + prices[i])
  }
  return sell
};

let prices = [1.2.3.0.2]
console.log(maxProfit(prices))
Copy the code

In memory, exactly 100 questions, but the road has just begun!

The road is long, I see no end, I will search high and low

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference