Skip to content

Latest commit

 

History

History
15 lines (10 loc) · 838 Bytes

File metadata and controls

15 lines (10 loc) · 838 Bytes

188. Best Time to Buy and Sell Stock IV (Hard)

链接

题目:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
代码(github):https://github.com/illuz/leetcode

题意

给一个数组,prices[i] 表示第 i 天的交易值,也就是你在这天买入或卖出的交易值。
你可以买入及卖出最多k轮,不过你一个时间只能拥有一个股票,求最大盈利。

分析

只要理解了 123. Best Time to Buy and Sell Stock III 的那个 O(1) 空间的算法,这个也可以那样变形过来。

注意,如果 k 大于数组的大小的一半,那就可以每相邻两天都能买了,所以可以直接用 III 版本的算法 O(n) 解决。