LeetCode Best Time to Buy and Sell Stock IV

LeetCode Best Time to Buy and Sell Stock IV

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 k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).


这是股票买卖最难的一题!问最多进行k次交易能获得的最大收益是多少。参考网上题解1题解2

令mustSell[i][j]表示前i天最多交易j次能获得的最大收益,且第i天必须卖出;globalBest[i][j]表示前i天最多交易j次能获得的最大收益,不要求第i天必须卖出。则有如下递推关系:

  1. mustSell[i][j]=max(globalBest[i-1][j-1]+profit, mustSell[i-1][j]+profit)
  2. globalBest[i][j]=max(globalBest[i-1][j], mustSell[i][j])

解释一下,profit=prices[i]-prices[i-1]为第i-1天买入,第i天卖出的收益。

第一个公式中,前i天最多交易j次且第i天卖出的最大收益为“前i-1天最多交易j-1次的全局最大收益+第i-1天买入第i天卖出的收益”“前i-1天最多交易j次且第i-1天卖出的最大收益+第i-1天买入第i天卖出的收益”的较大者。第一部分好理解,第二部分为什么还是j次交易呢,第一眼看上去好像有j+1次交易了,但是因为mustSell[i-1][j]表示第i-1天必须卖出,而profit表示第i-1天要买入,第i天卖出,两者加起来的效果相当于第i-1天的卖出买入抵消了,即交易次数还是j次,而且恰好变成了第i天卖出,和mustSell[i][j]的含义一致。

第二个公式就好理解了,前i天最多交易j次的全局最大收益为“最后一次交易不在第i天发生,则globalBest[i-1][j]”与“最后一次交易在第i天发生,则mustSell[i][j]”的较大者。

如果允许交易的次数k很大,那么以上DP效率较低,可以换成LeetCode Best Time to Buy and Sell Stock II的贪心策略。因为一次交易至少涉及到两天,所以如果k>=prices.size()/2时,可以采用贪心策略。

完整代码如下:

class Solution {
public:
	int maxProfit(int k, vector<int>& prices) {
		int days = prices.size();
		if (days < 2)return 0;
		if (k >= days / 2) {
			int ans = 0;
			for (int i = 1; i < days; ++i) {
				if (prices[i] > prices[i - 1])ans += (prices[i] - prices[i - 1]);
			}
			return ans;
		}
		vector<vector<int>> mustSell(days, vector<int>(k + 1, 0)), globalBest(days, vector<int>(k + 1, 0));
		for (int i = 1; i < days; ++i) {
			int profit = prices[i] - prices[i - 1];
			for (int j = 1; j <= k; ++j) {
				mustSell[i][j] = max(globalBest[i - 1][j - 1] + profit, mustSell[i - 1][j] + profit);
				globalBest[i][j] = max(globalBest[i - 1][j], mustSell[i][j]);
			}
		}
		return globalBest[days - 1][k];
	}
};

本代码提交AC,用时9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *