8946: DP33 买卖股票的最好时机 IV
[Creator : ]
Description
假设你有一个数组 prices，长度为 n，其中 prices[i] 是某只股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益。
1. 你最多可以对该股票有 k 笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回 0
3. 假设买入卖出均无手续费
1. 你最多可以对该股票有 k 笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回 0
3. 假设买入卖出均无手续费
Input
第一行输入一个正整数 n 和一个正整数 k。表示数组 prices 的长度和 交易笔数
第二行输入 n 个正整数表示数组的所有元素值。
Output
输出最大收益
Constraints
$1 \leq n \leq 1,000$
$1 \leq k \leq 100$
$1 \leq price_i \leq 1,000$
$1 \leq k \leq 100$
$1 \leq price_i \leq 1,000$
Sample 1 Input
6 3
8 9 3 5 1 3
Sample 1 Output
5
第一天(股票价格=8)买进，第二天(股票价格=9)卖出，收益为1
第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为5。
Sample 2 Input
8 2
3 2 5 0 0 3 1 4
Sample 2 Output
7
第二天(股票价格=2)买进，第三天(股票价格=5)卖出，收益为3
第五天(股票价格=0)买进，第八天(股票价格=4)卖出，收益为4
总收益为7
Sample 3 Input
4 4
9 8 4 1
Sample 3 Output
0
HINT
相同题目：牛客网。