Leetcode - Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
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 | func maxProfit(prices []int) int { if len(prices) == 0 { return 0 } dp := make([][]int, 3) n := len(prices) for i := 0; i < len(dp); i++ { dp[i] = make([]int, n) } for k := 1; k <= 2; k++ { for i := 1; i < n; i++ { minP := prices[0] for j := 1; j <= i; j++ { minP = min(minP, prices[j] - dp[k-1][j-1]) } dp[k][i] = max(dp[k][i-1], prices[i]-minP) } } return dp[2][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)
