题目1057. 股票买卖 IV题目描述给定一个长度为N NN的数组数组中的第i ii个数字表示一个给定股票在第i ii天的价格。设计一个算法来计算你所能获取的最大利润你最多可以完成k kk笔交易。注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。一次买入卖出合为一笔交易。输入格式第一行包含整数N NN和k kk表示数组的长度以及你可以完成的最大交易笔数。第二行包含N NN个不超过10000 1000010000的非负整数表示完整的数组。输出格式输出一个整数表示最大利润。数据范围1 ≤ N ≤ 10 5 1≤N≤10^51≤N≤105,1 ≤ k ≤ 100 1≤k≤1001≤k≤100时空限制1s / 128MB输入样例13 2 2 4 1输出样例12输入样例26 2 3 2 6 5 0 3输出样例27样例解释样例1在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。样例2在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4 。随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。共计利润 43 7.思路代码#includeiostream#includecstringusingnamespacestd;constintMaxN1e510,MaxM10010;intN,M,w[MaxN],f[MaxN][MaxM][2];intmain(){cinNM;for(inti1;iN;i){cinw[i];}memset(f,-0x3f,sizeoff);for(inti0;iN;i){f[i][0][0]0;}for(inti1;iN;i){for(intj1;jM;j){f[i][j][0]max(f[i-1][j][0],f[i-1][j][1]w[i]);f[i][j][1]max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);}}intres0;for(intj1;jM;j){resmax(res,f[N][j][0]);}coutres;return0;}结果