Leetcode Best Time to Buy and Sell Stock III

``/*** 题目：https://oj.leetcode.com/problems/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).O(n^2)的算法非常easy想到：找寻一个点j，将原来的price[0..n-1]切割为price[0..j]和price[j..n-1]，分别求两段的最大profit。进行优化：对于点j+1，求price[0..j+1]的最大profit时，非常多工作是反复的，在求price[0..j]的最大profit中已经做过了。相似于Best Time to Buy and Sell Stock。能够在O(1)的时间从price[0..j]推出price[0..j+1]的最大profit。``

(prices[i] - min) : profitLeft[i - 1]; //min = prices[i] < min ? prices[i] : min; if(prices[i] - min > profitLeft[i -1]){//注意，此处不要写成if(prices[i] - min > profit){ profitLeft[i] = prices[i] - min; } else { profitLeft[i] = profitLeft[i - 1]; } if(prices[i] < min){ min = prices[i]; } } //store the maxProfit into profitRight[i], from right to left // profit = 0; max = prices[size - 1]; for(i = size - 2; i >= 0; i--){ if(max - prices[i] > profitRight[i + 1]){//注意，此处不要写成if(max - prices[i] > profit){ profitRight[i] = max - prices[i]; } else { profitRight[i] = profitRight[i + 1]; } if(prices[i] > max){ max = prices[i]; } } profit = profitRight[0] + profitLeft[0]; for(i = 1; i < size; i++){ if(profitRight[i] + profitLeft[i] > profit){ profit = profitRight[i] + profitLeft[i]; } } return profit; } };