<?php
class Solution {

    /**
     * @param Integer $k
     * @param Integer[] $prices
     * @return Integer
     */
    function maxProfit($k, $prices) {
        $res = 0;
        $len = count($prices);
        if($k > $len){
            for($i = 0; $i < $len - 1; $i++)
            {
                $h = $prices[$i + 1] - $prices[$i];
                if($h > 0){
                    $res += $h;
                }
            }

            return $res;
        }

        $buy = array_fill(0, $k+1, PHP_INT_MIN);
        $sell = array_fill(0, $k+1, 0);

        for($i = 0; $i < $len; $i++)
        {
            for($j = $k; $j > 0; $j--)
            {
                $sell[$j] = max($sell[$j], $buy[$j] + $prices[$i]);
                $buy[$j] = max($buy[$j], $sell[$j - 1] - $prices[$i]);
            }
        }
        return $sell[$k];
    }
}