买卖股票的最好时机(四)_牛客题霸

假设你有一个数组，长度为，其中是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益 1. 你最多可以对该股票有笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票 2. 如果不能获取收益，请返回0 3. 假设买入卖出均无手续费数据范围:

第一行输入一个正整数 n 和一个正整数 k。表示数组 prices 的长度和 交易笔数第二行输入 n 个正整数表示数组的所有元素值。

输出最大收益

示例1

输入

6 3
8 9 3 5 1 3

第一天(股票价格=8)买进，
第二天(股票价格=9)卖出，收益为1
第三天(股票价格=3)买进，
第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，
第六天(股票价格=3)卖出，收益为2
总收益为5。

示例2

8 2
3 2 5 0 0 3 1 4

第二天(股票价格=2)买进，
第三天(股票价格=5)卖出，收益为3
第五天(股票价格=0)买进，
第八天(股票价格=4)卖出，收益为4
总收益为7

示例3

4 4
9 8 4 1