leetcode188 买卖股票的最佳时机 IV

给定一个整数数组 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

思路：定义两个数组，分别代表第i次买入和第i次卖出，买入时要争取花费最小，而此时的花费相当于这次的价格减去上一次卖出时的利润，卖出时要争取利润最大，而此时的利润则等于这次的价格减去这一次的花费。从头到尾遍历股票价格，将这一次作为第i次买入和卖出与已有值比较，遍历到最后所得的最后一次所获得的利润即为总最大利润。

代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
vector<int> a(k+1,1111),b(k+1,0);
int i,j;
int n=prices.size();
for(i=0;i<n;i++)
{
for(j=1;j<=k;j++)
{
    a[j]=min(a[j],prices[i]-b[j-1]);
    b[j]=max(b[j],prices[i]-a[j]);
}
}
return b[k];
    }
};