leetcode_question_123 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).
앞의 두 문제와 비교하면 두 번의 거래가 제한되어 있어서 이 문제가 가장 어렵다.
i를 0에서 n-1로 설정하면 각 i를 대상으로 prices의 하위 서열 [0,..., i][i,..., n-1]에서 각각 얻은 최대 이윤(첫 번째 문제)을 보면 된다.
이렇게 초보적으로 계산하면 시간 복잡도는 O(n2)이다.
향상된 기능:
개선된 방법은 동적 기획이다. 바로 첫 번째 스캔이다. 먼저 하위 서열 [0,...,i]의 최대 이윤을 계산하고 하나의 수조로 저장하면 시간은 O(n)이다.
두 번째 단계는 역방향 스캐닝으로 하위 서열 [i,..., n-1]의 최대 이윤을 계산한다. 이 단계는 이전 단계의 결과와 결합하여 최종 최대 이윤을 계산할 수 있다. 이 단계도 O(n)이다.
그래서 마지막 알고리즘의 복잡도는 O(n)이다.

int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int length = prices.size();
    	if(length < 2) return 0;
		//profit from 0 to i
		int* profitleft = new int[length];
		profitleft[0] = 0;
		int lowprice = prices[0];
		for(int i = 1; i < length; ++i)
		{
			if(prices[i] > lowprice)
			{
				int tmp = prices[i] - lowprice;
				if(tmp > profitleft[i-1])
					profitleft[i] = tmp;
				else
					profitleft[i] = profitleft[i-1];
			}else{
				lowprice = prices[i];
				profitleft[i] = profitleft[i-1];
			}
		}
		//profit from i to n
		int* profitright = new int[length];
		profitright[length-1] = 0;
		int highprice = prices[length-1];
		for(int i = length-2; i >= 0; --i)
		{
			if(prices[i] < highprice)
			{
				int tmp = highprice - prices[i];
				if(tmp > profitright[i+1])
					profitright[i] = tmp;
				else
					profitright[i] = profitright[i+1];
			}else{
				highprice = prices[i];
				profitright[i] = profitright[i+1];
			}
		}
		//
		int max = 0;
		for(int i = 0; i < length; ++i)
		{
			int tmp = profitleft[i] + profitright[i];
			if(tmp > max) max = tmp;
		}
		return max;
    }

int maxProfit(vector<int> &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int length = prices.size();
    	if(length < 2) return 0;
		//profit from 0 to i
		int* profitleft = new int[length];
		profitleft[0] = 0;
		int lowprice = prices[0];
		for(int i = 1; i < length; ++i)
		{
			if(prices[i] > lowprice)
			{
				int tmp = prices[i] - lowprice;
				if(tmp > profitleft[i-1])
					profitleft[i] = tmp;
				else
					profitleft[i] = profitleft[i-1];
			}else{
				lowprice = prices[i];
				profitleft[i] = profitleft[i-1];
			}
		}
		int max = profitleft[length-1];
		//profit from i to n
		int* profitright = new int[length];
		profitright[length-1] = 0;
		int highprice = prices[length-1];
		for(int i = length-2; i >= 0; --i)
		{
			if(prices[i] < highprice)
			{
				int tmp = highprice - prices[i];
				if(tmp > profitright[i+1])
					profitright[i] = tmp;
				else
					profitright[i] = profitright[i+1];
			}else{
				highprice = prices[i];
				profitright[i] = profitright[i+1];
			}
			int tmpmax = profitleft[i] + profitright[i];
			if(tmpmax > max) max = tmpmax;
		}
		return max;
    }