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 k transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
题意:
一个数组第i个元素是表示股票在第i天的价格,只允许最多完成k次交易,设计一个找到最大收益的算法。
注意:不能从事多个交易在同一时间(即,你必须卖出股票后,才能再次购买股票)。
思路:
典型的动态规划股票问题,这应该是股票问题中最难的,完成k次交易,获得最大收益。思路同121. Best Time to Buy and Sell Stock,122. Best Time to Buy and Sell Stock II,123. Best Time to Buy and Sell Stock III,利用动态规划的局部最优构造全局最优的思想解决问题。
方法一:
1 | 题目的关键是下面的动态转移方程: |
1 | 这一题的难度要远高于前面几题,需要用到动态规划,但是需要额外的辅助。 |
1 | //“局部最优和全局最优解法” |
方法二:
不太懂的一个方法,思路同123. Best Time to Buy and Sell Stock III方法二,代码简洁,但是不太理解。
1 | class Solution { |