都是用动态规划去做;
123题
class Solution {
public:
int maxProfit(vector<int>& prices) {
int size=prices.size();
int buy1=-prices[0],sell1=0,buy2=-prices[0],sell2=0;
for(int i=1;i<size;++i)
{
sell2=max(sell2,buy2+prices[i]);
buy2=max(buy2,sell1-prices[i]);
sell1=max(sell1,buy1+prices[i]);
buy1=max(buy1,-prices[i]);
}
return sell2;
}
};
188题
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size()<2)
return 0;
vector<int> dp(2*k+1,0);
for(int i=1;i<=k;++i)
dp[2*i-1]=-prices[0];
for(int p:prices)
for(int i=1;i<=2*k;++i)
// {if(i%2)
// dp[i]=max(dp[i],dp[i-1]-p);
// else
// dp[i]=max(dp[i],dp[i-1]+p);
dp[i]=max(dp[i],(1-i%2*2)*p+dp[i-1]);
return dp[2*k];
}
};