Best Time to Buy and Sell Stock IV
题意：
用一个数组表示股票每天的价格，数组的第i个数表示股票在第i天的价格。最多交易k次，手上最多只能持有一支股票，求最大收益
代码
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if(prices.size() < 2)
return 0;
//当k大于天数时，就是 Best Time to Buy and Sell Stock II 了，不需要动态规划
if(k >= prices.size())
return maxProfit2(prices);
int n = prices.size();
vector<int> temp(k+1,0);
vector<vector<int>> local(n,temp);
vector<vector<int>> globle(n,temp);
for(int i = 1;i<n;i++){
int diff = prices[i] - prices[i-1];
for(int j = 1;j<=k;j++){
local[i][j] = max(globle[i-1][j-1]+diff,local[i-1][j] + diff);
globle[i][j] = max(globle[i-1][j],local[i][j]);
}
}
return globle[n-1][k];
}
int maxProfit2(vector<int> &prices){
int maxProfit = 0;
for(int i = 1;i<prices.size();i++){
int gas = prices[i] - prices[i-1];
if(gas > 0){
maxProfit += gas;
}
}
return maxProfit;
}
};
分析
用local[i][j]表示到达第i天时，最多进行j次交易的局部最优解；用global[i][j]表示到达第i天时，最多进行j次的全局最优解。它们二者的关系如下（其中diff = prices[i] – prices[i – 1]）：
local[i][j] = max(globle[i-1][j-1]+diff,local[i-1][j] + diff);
globle[i][j] = max(globle[i-1][j],local[i][j]);
注意：当k大于天数时，就是 Best Time to Buy and Sell Stock II 了，不需要动态规划
扩充
Best Time to Buy and Sell Stock
题意
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2)
return 0;
int maxProfit = 0;
int curMin = prices[0];
for(int i = 1;i<prices.size();i++){
curMin = min(curMin,prices[i]);
maxProfit = max(maxProfit,prices[i] - curMin);
}
return maxProfit;
}
};
分析
动态规划法。从前向后遍历数组，记录当前出现过的最低价格，作为买入价格，并计算以当天价格出售的收益，作为可能的最大收益，整个遍历过程中，出现过的最大收益就是所求。
Best Time to Buy and Sell Stock II
题意
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2 )
return 0;
int profit = 0;
vector<int>::iterator it = prices.begin();
for(++it;it!=prices.end();it++){
int gap = *it-*(it-1);
if(gap > 0)
profit += gap;
}
return profit;
}
};
分析
贪心法。从前向后遍历数组，只要当天的价格高于前一天的价格，就算入收益。
Best Time to Buy and Sell Stock III
题意
Description: Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2)
return 0;
int n = (int)prices.size();
vector<int> preProfit(n,0);
vector<int> postProfit(n,0);
int curMin = prices[0];
for(int i = 1;i < n;i++){
curMin = min(curMin,prices[i]);
preProfit[i] = max(preProfit[i-1],prices[i] - curMin);
}
int curMax = prices[n-1];
for(int i = n-2;i>=0;i--){
curMax = max(curMax,prices[i]);
postProfit[i] = max(postProfit[i+1], curMax - prices[i]);
}
int maxProfit = 0;
for(int i = 0; i <n; i++){
maxProfit = max(maxProfit,postProfit[i]+preProfit[i]);
}
return maxProfit;
}
};
分析
动态规划法。以第i天为分界线，计算第i天之前进行一次交易的最大收益preProfit[i]，和第i天之后进行一次交易的最大收益postProfit[i]，最后遍历一遍，max{preProfit[i] + postProfit[i]} (0≤i≤n-1)就是最大收益。第i天之前和第i天之后进行一次的最大收益求法同Best Time to Buy and Sell Stock I。
注意：本题就是k=2时，Best Time to Buy and Sell Stock IV的情况
Best Time to Buy and Sell Stock with Cooldown
题意
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
代码
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 2){
return 0;
}
int curBuy = -prices[0];
int curSell = 0;
int preSell = 0;
int n = prices.size();
for(int i = 1;i<n;i++){
int temp = curSell;
curSell = max(curSell,curBuy + prices[i]);
if(i > 1){
curBuy = max(curBuy,preSell-prices[i]);
}else{
curBuy = max(curBuy,-prices[i]);
}
preSell = temp;
}
return curSell;
}
};
分析
curBuy,表示在第i天买入股票所能获得的最大累积收益
curSell,表示在当天卖出股票所能获得的最大累积收益
preSell,表示在前一天卖出股票所能获得的最大累积收益
