源题目

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

188. 买卖股票的最佳时机 IV

难度困难561
给定一个整数数组 prices ，它的第 _i 个元素 prices[i] 是一支给定的股票在第 i _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

通过次数83,841
提交次数216,243

思路
（1）当k大于等于数组长度一半时, 问题退化为贪心问题此时采用 买卖股票的最佳时机 II的贪心方法解决可以大幅提升时间性能
（2）对于其他的k, 可以采用 买卖股票的最佳时机 III的方法来解决, 在III中定义了两次买入和卖出时最大收益的变量, 在这里就是k租这样的
变量, 即问题IV是对问题III的推广, buy[i]和sell[i]分别表示第i比交易买入和卖出时各自的最大收益

class Solution {
    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($k, $prices) {
        $len = count($prices);
        if($k < 1 || !$prices) return 0;
        if($k >= $len/2) return $this->greedy($prices);
        $buy = [-$prices[0], -$prices[0]];//考虑边界问题
        $sell = [0, 0];
        foreach($prices as $p){
            $buy[0] = max($buy[0], -$p);
            $sell[0] = max($sell[0], $buy[0] + $p);//卖出第一笔
            for($i = 1; $i < $k; ++ $i){
                $buy[$i] = max($buy[$i], $sell[$i -1] - $p);
                $sell[$i] = max($sell[$i], $buy[$i] + $p);
            } 
        }
        return $sell[$k -1];
    }
    function greedy($prices){
        $ret = 0;
        $len = count($prices);
        for($i = 1; $i < $len; ++$i){
            if($prices[$i] > $prices[$i - 1]){
                $ret += $prices[$i] - $prices[$i - 1];
            }
        }
        return $ret;
    }
}