LeetCode Best Time to Buy and Sell Stock III

LeetCode Best Time to Buy and Sell Stock III

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).


股票买卖题三。这次限制最多交易两次,问最大能获利多少。这确实是个hard题,研一卜神算法作业中遇到过。

先来回顾一下股票买卖第一题LeetCode Best Time to Buy and Sell Stock,当时的做法是从左往右找到除了当前值的最小值min_so_far,然后用当前值减去min_so_far,表示如果在当前卖出(即用min_so_far买入)能获得的最大收益profit1。这一题允许最多两次交易,那么如果求到在当前买入能获得的最大收益profit2,则profit1+profit2表示在当前卖出后买入能获得的最大收益。计算所有的profit1+profit2的最大值,就是两次交易能获得的最大收益。

计算profit2的方法和计算profit1类似,此时我们从右往左找到除了当前值的最大值max_so_far,则用max_so_far减去当前值,就表示在当前买入(max_so_far卖出)能获得的最大收益profit2。

整理一下思路:我们尝试把每个点作为两次交易的分界点,那么这个点在上一个交易中卖出了,同时在下一个交易中买入了,我们要分别求到在这个点卖出和买入能获得的最大收益,然后把两个值加起来就是在这个点两次交易的最大收益。求所有点的最大收益的最大值就是最终结果。

举个例子,如下表,表中的min_so_far和profit1是从左往右计算的,max_so_far和profit2是从右往左计算的,profit1/2计算的都是当前profit和历史profit的最大值,和代码中的含义一致。

prices 3 2 6 5 0 3
min_so_far INT_MAX 3 2 2 2 0
max_so_far 6 6 5 3 3 INT_MIN
profit1 0 0 4 4 4 4
profit2 4 4 3 3 3 0
total 4 4 7 7 7 4

完整代码如下:

class Solution {
public:
	int maxProfit(vector<int>& prices) {
		int n = prices.size();
		if (n < 2)return 0;
		vector<int> minprice(n), maxprice(n);
		for (int i = 0; i < n; ++i) {
			minprice[i] = i == 0 ? INT_MAX : min(minprice[i - 1], prices[i - 1]);
			maxprice[n - i - 1] = i == 0 ? INT_MIN : max(maxprice[n - i], prices[n - i]);
		}
		vector<int> profit1(n), profit2(n);
		for (int i = 0; i < n; ++i) {
			profit1[i] = i == 0 ? 0 : max(profit1[i - 1], prices[i] - minprice[i]);
			profit2[n - i - 1] = i == 0 ? 0 : max(profit2[n - i], maxprice[n - i - 1] - prices[n - i - 1]);
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			ans = max(ans, profit1[i] + profit2[i]);
		}
		return ans;
	}
};

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

Leave a Reply

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