这道题更简单，我们只要算出所有递增序列的和就行了。值得讨论的是根据这一题观察出来的其他结论，代码如下：
我们可以看出以下两点：
- 递增序列的数量就是我们能最大化利润要买的次数，超过了这个次数，我们最大利润不会增加
- 假设现在能买k次，如果我们允许多买一次那么profit(k + 1) >= profit(k)，因为如果当前有序列不是递增序列，我们可以通过多买一次把它分成递增序列或者部分递增序列，或者除此之外还有别的递增序列，直到我们找到所有递增序列之后，利润不会增长
这道题还可以用DP的思路来解，用dp[i]表示前i + 1天的最大利润，我们有递推公式：
- localMax = max(dp[j] + prices[i] - prices[j]), where 0 <= j < i
- dp[i] = max(dp[i - 1], localMax)
代码如下：
No comments:
Post a Comment