//问题：股票买卖问题4（最多交易k次，这里一次交易指买+卖）
/*
* 方法：DP法(找递推公式)
* 解释：与问题3的方法类似，每次操作与上次操作有关，确保每次操作的收益最大
如果k >= len/2，则和问题1一样，相当于买卖次数没有限制，直接用求全局最优即可
buy[i][j-1]表示对于j-1天，第i次买入后的最大收益，为了节省空间可写成单变量buy
sell[i][j] 表示对于j天，第i次卖出后的最大收益
递推公式：
buy = max( buy, sell[i-1][j-1] - a[j-1] )
//j-1天,第i次买入（承接j-1天，第i-1次卖出,sell[i-1][j-1]），对应第j-1天不买，或者买（则减去a[j-1]）
sell[i][j] = max( sell[i][j-1], buy + a[j] )
//j天,第i次卖出（承接j-1天第i次买入），对应第j天不卖（sell[i][j-1]）或者卖(则加上a[j])
了解即可！！
*/
#include <algorithm>
#include <climits>
class Solution
{
public:
int maxProfit(int k, vector<int>& a)
{
if(a.empty()) return 0;
int n = a.size();
if(k >= n/2) //如果买卖次数没有限制，则直接全局处理，变为问题二
{
int maxprofit = 0;
for(int i = 1; i < n; i++)
{
if(a[i] > a[i-1]) maxprofit += a[i] - a[i-1];
}
return maxprofit;
}
vector<vector<int>> sell(k+1, vector<int>(n));//交易次数多开辟一段空间，以提供初值，以及索引方便
for(int i = 1; i <= k; i++) //遍历交易次数，i=1~k
{
int buy = sell[i-1][0]-a[0]; //初始化
for(int j = 1; j<n; j++) //遍历天数，j=1~n-1(天数从0开始，式中有j-1)
{
//buy从a[0]开始，sell从a[1]开始，错开以避免重复交易
buy = max(buy, sell[i-1][j-1]-a[j-1]); //j-1天第i次买入后的收益，(注意这里与sell[i-1][j-1]相比较，有承接性，以避免多次交易重复买卖)
sell[i][j] = max(sell[i][j-1], buy+a[j]); //j天第i次卖出之后的收益
}
}
return sell[k][n-1]; //返回第k次卖出后的收益
}
};
/*
了解即可
问题：买卖多次，但是有冷冻期，卖出股票后要间隔一天才能再次买入
方法：动态规划
buy[i]表示在第i天之前最后一个操作是买，此时的最大收益
sell[i]表示在第i天之前最后一个操作是卖，此时的最大收益
则有递推式：
buy[i] = max(sell[i-2] - price, buy[i-1]) i天，买入收益，第i天买（由于存在一天的冷冻期，承接i-2天的卖出收益sell[i-2]）或者不买（承接buy[i-1]）
sell[i] = max(buy[i-1] + price, sell[i-1]) i天，卖出收益，第i天卖（承接buy[i-1）,或者不卖（承接sell[i-1]）
由于i只依赖于i-1和i-2，所以我们可以在O(1)的空间复杂度完成算法
*/
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int buy = INT_MIN, pre_buy = 0, sell = 0, pre_sell = 0;
for (int price:prices)
{
pre_buy = buy;
buy = max(pre_sell - price, pre_buy);//i天的买入收益与i-2天的卖出收益有关
pre_sell = sell;
sell = max(pre_buy + price, pre_sell); //i天的卖出收益与i-1天的买入收益有关
}
return sell;
}
};
