“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Topic describes

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

Example 1:

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

Example 2:

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.

Tip:

  • 0 <= k <= 100
  • 0 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Analysis of the

When k is greater than or equal to half of the array length, the problem degenerates into a greedy problem. In this case, the greedy solution of the best time to buy and sell stocks II can greatly improve the time performance. For other k, the solution can be solved by the best time to buy and sell stocks III. In III, the variable of maximum return when buying and selling twice is defined, in this case, it is a variable like k rent, that is, question IV is the promotion of question III, and T [I][0] and T [I][1] respectively represent the maximum return when buying and selling in the I ratio transaction.

Solution: dynamic programming
var maxProfit = function(k, prices) {
    if (prices.length == 0) return 0
    var dp = new Array(prices.length).fill(' ').map(d= >new Array(k*2+1).fill(0))
    for (var i = 0 ; i < prices.length ; i++) {
        if (i == 0) {
            dp[0] [0] = 0// The first day I have no money in stocks
            for (var m = 0 ; m < k*2; m=m+2) {
                dp[i][m+1] = -prices[0]// Hold your money in stocks for the KTH time on the first day
            }
            continue
        }
        for (var j = 0 ; j < k*2; j=j+2) {
            dp[i][0] = dp[i-1] [0]
            dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i])
            dp[i][j+2] = Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i])
        }
    }
    return dp[prices.length-1][k*2]};Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤