中国关键词网站,自媒体平台收益,装修设计怎么学,google浏览器官方dp
1、123. 买卖股票的最佳时机 III
题目#xff1a; 给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意#xff1a;你不能同时参与多笔交易#xff08;你必须在再次购…dp
1、123. 买卖股票的最佳时机 III
题目 给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
func maxProfit(prices []int) int {dp : make([][]int, len(prices))for i : 0; i len(prices); i {dp[i] make([]int, 5)}dp[0][0] 0dp[0][1] -prices[0]dp[0][2] 0dp[0][3] -prices[0]dp[0][4] 0for i : 1; i len(prices); i {dp[i][0] dp[i-1][0]dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i])dp[i][2] max(dp[i-1][2], dp[i-1][1] prices[i])dp[i][3] max(dp[i-1][3], dp[i-1][2] - prices[i])dp[i][4] max(dp[i-1][4], dp[i-1][3] prices[i])}return dp[len(prices)-1][4]
}
func max(a, b int) int {if a b {return a}return b
}2、188.买卖股票的最佳时机IV
题目 给你一个整数数组 prices 和一个整数 k 其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说你最多可以买 k 次卖 k 次。
注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
// 买卖股票的最佳时机IV 动态规划
// 时间复杂度O(kn) 空间复杂度O(kn)
func maxProfit(k int, prices []int) int {if k 0 || len(prices) 0 {return 0}dp : make([][]int, len(prices))status : make([]int, (2 * k 1) * len(prices))for i : range dp {dp[i] status[:2 * k 1]status status[2 * k 1:]}for j : 1; j 2 * k; j 2 {dp[0][j] -prices[0]}for i : 1; i len(prices); i {for j : 0; j 2 * k; j 2 {dp[i][j 1] max(dp[i - 1][j 1], dp[i - 1][j] - prices[i])dp[i][j 2] max(dp[i - 1][j 2], dp[i - 1][j 1] prices[i])}}return dp[len(prices) - 1][2 * k]
}func max(a, b int) int {if a b {return a}return b
}
