问题描述
You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.
Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
Example 2:
Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6
Constraints:
- 1 <= prices.length <= 5 * 10^4
- 1 <= prices[i] < 5 * 10^4
- 0 <= fee < 5 * 10^4
问题分析
这里采用dp方式去求解：dp[i]表示prices中下标从i开始到最后一天的最大获利，dp[0]为最终答案。
因此我们首先初始化2个base case:
dp[len(prices)-1] = 0
dp[len(prices)-2] = max(0, prices[length-1]-prices[length-2]-fee)
然后倒着计算，直至计算到dp[0]
在计算过程中，我们将第i天看做买入时间点，对于[i+1, len(prices)-1]这个区间，依次当做出售点，计算过程中的最大获利，然后更新dp[i]为这个最大获利值。在遍历过程中，假设sellday为k，那么获利为 prices[k] - prices[i] - fee + dp[k+1]。由于我们是逆序计算的，dp[k+1]已经已知，因此可以避免递归调用。整体时间复杂度为O(N^2)
由此，我们可以写出以下解决方法：(可惜TLE了。。。。)
初始解法
var donemap map[int]int
// TLE
func maxProfit(prices []int, fee int) int {
if len(prices) < 2 {
return 0
}
donemap = make(map[int]int)
length := len(prices)
donemap[length-1] = 0
donemap[length-2] = max(0, prices[length-1]-prices[length-2]-fee)
for i := length - 3; i >= 0; i-- {
calcProfitReverse(prices, i, fee)
}
return donemap[0]
}
func calcProfitReverse(prices []int, startPos int, fee int) {
buyday := startPos
ans := donemap[startPos+1]
if prices[startPos] >= prices[startPos+1] {
donemap[startPos] = ans
return
}
for sellday := startPos + 1; sellday < len(prices); sellday++ {
if prices[sellday]-fee <= prices[buyday] {
continue
}
tmpans := prices[sellday] - prices[buyday] - fee
if sellday < len(prices)-1 {
tmpans += donemap[sellday+1]
}
if tmpans > ans {
ans = tmpans
}
}
donemap[startPos] = ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
优化解法
在讨论区发现一个高票解答，也是dp方式，只不过要巧妙很多：
我们不再只定义一个dp数组，而是两个：buy 和 sell
buy[i]表示到第i天为止最后一个动作是buy的最大利润
sell[i]表示到第i天为止最后一个动作是sell的最大利润
那么由此，我们可以得到状态转移公式为：
sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)
buy[i] = max(buy[i-1], sell[i-1]-prices[i])
对于sell[i]，它有2种情况:
- 第i天不进行sell，那么
sell[i]就等于sell[i-1] - 第i天进行sell动作，那么当天的获利为
prices[i]-fee，再加上到第i-1天为止最后一个动作为buy的最大利润，即buy[i-1]
这2种情况，取较大值即可；buy[i]同理
具体代码如下：
func maxProfitV2(prices []int, fee int) int {
// 第i天为止最后一个动作是buy的最大利润
// buy[i] = max(buy[i-1], sell[i-1]-prices[i])
buy := make([]int, len(prices))
// 第i天为止最后一个动作是sell的最大利润
// sell[i] = max(sell[i-1], buy[i-1]+prices[i])
sell := make([]int, len(prices))
// base case
// 第1天无股票可卖，因此sell[0]为0
sell[0] = 0
// 第1天买，对于收益而言，则为购买花费的负数，即 -prices[0]
buy[0] = -1 * prices[0]
for i := 1; i < len(prices); i++ {
sell[i] = max(sell[i-1], buy[i-1]+prices[i]-fee)
buy[i] = max(buy[i-1], sell[i-1]-prices[i])
}
return sell[len(prices)-1]
}