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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | 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} |
评论 (0)
