Leetcode - Best Time to Buy and Sell Stock IV

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

func maxProfit(k int, prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    n := len(prices)
    
    if k >= n/2 {
        maxP := 0
        for i := 1; i < n; i++ {
            if prices[i] - prices[i-1] > 0 {
                maxP += prices[i] - prices[i-1]
            }
        }
        return maxP
    }
    dp := make([][]int, k+1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, n)
    }
    for m := 1; m <= k; m++ {
        for i := 1; i < n; i++ {
            minP := prices[0]
            for j := 1; j <= i; j++ {
                minP = min(minP, prices[j]-dp[m-1][j-1])
            }
            dp[m][i] = max(dp[m][i-1], prices[i]-minP)
        }
    }
    return dp[k][n-1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章