# Leetcode - Best Time to Buy and Sell Stock IV

violet posted @ Jun 16, 2020 02:26:16 AM in 算法 with tags Algorithm DP Golang , 378 阅读

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
}

(输入验证码)
or Ctrl+Enter