preface

A series of interview questions with high appearance rate, within half a year, headlines 18 times, Ali 4 times, Millet 3 times (I bought a member so you can see the appearance rate). A must-see for a recent interview.

121. The Best Time to Buy and sell Stocks (Easy)

The original problem

Given an array, its ith element is the price of a given stock on the ith day. If you only allow one trade (buy and sell one stock), design an algorithm to calculate the maximum profit you can make. Note that you can’t sell a stock before you buy it.

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 greater than the buying price.Copy the code

Example 2:

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

Train of thought

Note: In this question, the maximum number of transactions is 1.

  • The first day I

    • If the firstiDays hold stocks. There are two possibilities at number oneiDays hold stocks.
      1. Buy stocks today
      2. You bought stocks before today
    • If the firstiDays do not hold stocks. There are two possibilities at number oneiDays do not hold stocks.
      1. I don’t own stocks today
      2. Sell your own stocks today

  • On day one, the stock price was 7

    • By buying stock is an expense, so if you buy stock on the first day, the maximum profit is0 minus 7 is minus 7
    • On the first day, I don’t own any stocks0

  • The next day, the stock price is 1

    • We need to maximize profits, so the lower the share price we buy, the better. The stock price on the second day is1Is better than the first day7, so we should choose to buy the stock on the second day, when the maximum profit is0 minus 1 is minus 1. (Since this case itself limits the number of transactions, there is no dividendIs not equal to0The situation)
    • If you don’t own the stock the next day, there are two possibilities. Or, sell your current holdings at ️’s share price today.) . The first possibility, the maximum payoff is zero0The second possibility is that the maximum payoff is1 minus 7 is minus 6That is less than0. So our maximum benefit on day two should be0.

  • On day 3, the stock price is 5

    • The stock price on day 3 is zero5It is higher than the previous day, so we still choose to buy the stock on the previous day, and the maximum profit on the third day when holding the stock is still- 1
    • On the third day, I don’t own the stock. There are two possibilities. The first possibility is that we can do what we did the day before and still get zero0. The second possibility is to sell your current holdings at today’s price for a gain of 15 minus 1 is 4(the current share price – the optimal value or lowest cost of owning the stock the previous day), the result is4Better than the first possibility. So the maximum gain from not owning the stock on day 3 is zero4.

I’m just going to go back and figure out the maximum value in the array of optimal outcomes for not owning stocks. 💡 (There is no burden when you do not own stocks.)

code


var maxProfit = function(prices) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    // DP1 array stores the I day, holding the maximum profit of the stock
    const dp1 = []
    dp1[0] = -prices[0]
    // Dp2 array stores the I day, does not hold the maximum profit of the stock
    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {
        dp1[i] = Math.max(dp1[i - 1], -prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])}return dp2[dp2.length - 1]};Copy the code

122. The Best Time to Buy and Sell Stocks II (Easy)

The original problem

Given an array, its ith element is the price of a given stock on the ith day. Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

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

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Train of thought

(309, 714) The number of transactions is not limited.

You can make an infinite number of transactions. So our gains can add up. The effect on the transition equation, most immediately, is that for the optimal solution to hold the stock on day I we need to consider the previous day’s return instead of starting at zero. So, the state transition equation for holding the stock changes from Max(the previous day’s state, 0 – today’s stock price) to Max(the previous day’s state, the previous day’s optimal return – today’s stock price).

We can follow the logic of the derivation above, and so on. Finally, return the best return on the last day when you didn’t own the stock.

code


/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    
    const dp1 = []
    dp1[0] = -prices[0]
    
    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {
        dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])}return dp2[prices.length - 1]};Copy the code

714. Best time to Buy and sell stocks including fees (medium)

The original problem

Given an array of integers prices, the ith element represents the stock price on the ith day; The non-negative integer fee represents the processing cost of trading shares. You can complete transactions as many times as you want, but you’ll have to pay a fee for each transaction. If you have already bought a stock, you cannot continue to buy it until you have sold it. Returns the maximum profit earned.

Example 1:

Input: prices = [1, 3, 2, 8, 4, 9], fee = 2 Output: 8 Explanation: Maximum profit that can be achieved: Total profit: ((8-1) -2) + ((9-4) -2) = 8 total profit: ((8-1) -2) + ((9-4) -2) = 8Copy the code

Train of thought

We only need to consider the fee when selling the stock.

code


/** * @param {number[]} prices * @param {number} fee * @return {number} */
var maxProfit = function(prices, fee) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    
    const dp1 = []
    dp1[0] = -prices[0]

    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {
        dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1] - fee)
    }
    
    return dp2[dp2.length - 1]};Copy the code

309. Best time to buy and sell stocks including freezing period (medium)

The original problem

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).

Example:

Input: [1,2,3,0,2] output: 3 explanation: the corresponding trading states are: [buy, sell, freeze period, buy, sell]Copy the code

Train of thought

This is still a variation of 122, but with some differences.

Trade stock cent is bought, sell two steps. Buying is subject to the freeze period, but selling is not. According to the rules of the freeze period, we need to adjust the state transfer equation of the holding stock as shown in the figure above. But many people look at the formula above and ask the following question.

🤔️Q: Why is the optimal state of holding stocks on day I obtained from the state of not holding stocks on day I-2, is day I-1 necessarily a freeze period?

😆A: There are two possible ways to own stocks on day I. The first possibility is to own the stock and continue for I minus 1 days. The second possibility is to buy the stock at the price of day I, so we have to think about day I minus day 1 without owning the stock.

If day I-1 is the freezing period. So the state on day i-1 must be the same as the state on day i-2.

If day I-1 is not the freezing period. There are two possibilities. The first possibility is that day I-1 itself doesn’t own the stock, so we need to get the state of day i-2. The second possibility is to sell the stock on day I-1, but because of the freeze period, you can’t buy the stock on day I, so this possibility doesn’t hold (we can’t sell the stock on day I-1 with or without the freeze period).

It can be seen from the above analysis. Whether day I-1 is a freeze period or not, we’re going to calculate from the optimal solution for day I-2 where we don’t own the stock.

code


/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    
    const dp1 = []
    dp1[0] = -prices[0]

    const dp2 = []
    dp2[0] = 0
    
    for (let i = 1; i < prices.length; i++) {
        let temp = dp2[i - 2= = =undefined ? 0 : dp2[i - 2]
        dp1[i] = Math.max(dp1[i - 1], temp - prices[i])
        dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])}return dp2[dp2.length - 1]};Copy the code

123. The Best time to Buy and sell stocks III (Difficulty)

The original problem

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

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

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

Example 1:

Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), the exchange will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit of 4-1 = 3.Copy the code

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Train of thought

So we’re going to have to add a little bit of latitude, because before we only had to think about holding and not holding, so we’re going to go from two cases to four cases. If you own the stock, you have two more opportunities to trade, if you own the stock, you have one more opportunity to trade, if you don’t own the stock, you have one more opportunity to trade.

code


/** * @param {number[]} prices * @return {number} */
var maxProfit = function(prices) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    
    // Hold stock
    const dp1 = [
        [-prices[0]], // There are two trades left
        [-prices[0]] // There is only one trade left
    ]
    // Do not own stock
    const dp2 = [
        [0].// There are two trades left
        [0] // There is only one trade left
    ]
    
    for (let i = 1; i < prices.length; i++) {
        // Hold the stock and have two more trading opportunities
        dp1[0][i] = Math.max(dp1[0][i - 1], -prices[i])
        // Hold stocks and have one more trading opportunity
        dp1[1][i] = Math.max(dp1[1][i - 1], dp2[0][i - 1] - prices[i])
        // Do not own the stock, there are two trading opportunities
        dp2[0][i] = Math.max(dp2[0][i - 1], prices[i] + dp1[0][i - 1]) 
        // Do not own the stock, there is one trading opportunity
        dp2[1][i] = Math.max(dp2[1][i - 1], prices[i] + dp1[1][i - 1])}return dp2[1][prices.length - 1]};Copy the code

188. The best time to Buy and sell stocks IV (Difficulty)

The original problem

Given an array, its ith element 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).

Example 1:

Input: [2,4,1], k = 2 Output: 2 Explanation: If you buy on day 1 (stock price = 2) and sell on day 2 (stock price = 4), the exchange will make a profit = 4-2 = 2.Copy the code

Example 2:

Input: [3,2,6,5,0,3], k = 2 Output: 7 Explanation: If you buy on day 2 (stock price = 2) and sell on day 3 (stock price = 6), the exchange will make a profit = 6-2 = 4. 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

Train of thought

In the leetcode use case, because k is too large, dp array is too large, resulting in memory overflow.

An array of length N makes at most n over 2 transactions, so if k is greater than n over 2, that means there’s no limit on the number of transactions, and we can treat this as problem 122.

code


/** * @param {number} k * @param {number[]} prices * @return {number} */
var maxProfit = function(k, prices) {
    if (prices.length === 0 || prices.length === 1) {
        return 0
    }
    
    if (k === 0) {
        return 0
    }
    
    if (k > prices.length / 2) {
        k = - 1
    }
    
    const dp1 = []
    const dp2 = []
    
    if (k == - 1) {
        dp1[0] = -prices[0]
        dp2[0] = 0
    } else {
        for (let i = 0; i < k; i++) {
            dp1.push([-prices[0]])
            dp2.push([0])}}for (let i = 1; i < prices.length; i++) {
        if (k === - 1) {
            dp1[i] = Math.max(dp1[i - 1], dp2[i - 1] - prices[i])
            dp2[i] = Math.max(dp2[i - 1], prices[i] + dp1[i - 1])}else {
            for (let j = 0; j < k; j++) {
                if (j === 0) {
                    dp1[j][i] = Math.max(dp1[j][i - 1], -prices[i]) 
                } else {
                    dp1[j][i] = Math.max(dp1[j][i - 1], dp2[j - 1][i - 1] - prices[i])
                }
                dp2[j][i] = Math.max(dp2[j][i - 1], prices[i] + dp1[j][i - 1]) 
                dp2[j][i] = Math.max(dp2[j][i - 1], prices[i] + dp1[j][i - 1])}}}if (k === - 1) {
        return dp2[prices.length - 1]}else {
        return dp2[k - 1][prices.length - 1]}};Copy the code

QA

🤔️Q: Today’s optimal solution is based on the optimal solution of the previous day. Does this guarantee global optimization?

😆A: We can treat each day as if it were our last. On the last day, our ️ earnings value is based on two possibilities. The first possibility is that on the last day, we don’t have any stock, and since it’s the last day, we can’t buy any stock, we can only maintain the previous day’s gains. The second possibility, finally we just have stock, we can only choose to sell it, our return depends on the day’s share price and buy price (the optimal value of owning stocks), share price is sure and certain that day, and if the buying price is not the optimal value, we must not get the maximum benefits.

reference

Most consistent ways of dealing with the series of stock problems