LeetCode 123. Best Time to Buy and Sell Stock III

895 ワード

LeetCode 121.Best Time to Buy and Sell Stockは、取引の最大利益を求めることができることを知っています.
この問題は2回まで取引を行うことを要求して、問題はpricesをどのように2つのセグメントに分けて、この2つのセグメントの最大利益を加算して最大利益を得ることができます.
複雑度O(n).
コード:
class Solution
{
public:
	int maxProfit(vector<int>& prices)
	{
		if (prices.size() <= 1)
		{
			return 0;
		}

		vector<int> first_time(prices.size(), 0);
		int min_price = prices.front();
		for (size_t i = 1; i < prices.size(); ++ i)
		{
			min_price = min(min_price, prices[i]);
			first_time[i] = max(first_time[i-1], prices[i]-min_price);
		}
		int max_price = prices.back();
		int max_profit = *max_element(first_time.begin(), first_time.end());
		for (int i = prices.size()-2; i >= 1; -- i)
		{
			max_price = max(max_price, prices[i]);
			max_profit = max(max_profit, first_time[i-1] + max_price - prices[i]);
		}

		return max_profit;
	}
};