leetcode--Best Time to Buy and Sell Stock III

拼搏现实的明天。 2021-10-25 12:40 128阅读 0赞

Say you have an array for which the *i*th 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).

public class Solution {
        /**
    	 * To solve this problem, we use two array to save the max profit.
    	 * The running time is O(n)
    	 * 
    	 * @param prices --input price array
    	 * @return maximum profit 
    	 * @author Averill Zheng
    	 * @version 2014-06-04
    	 * @since JDK 1.7
    	 */
    	public int maxProfit(int[] prices) {
    		int maxProfit = 0;
    		int length = prices.length;
    		if(length > 0){
    			//maximum in order
    			int[] maxInOrder = new int[length];
    			maxInOrder[0] = 0; 
    			int min = prices[0];
    			for(int i = 1; i < length; ++i){
    				if(prices[i] - min >= maxInOrder[i - 1])
    					maxInOrder[i] = prices[i] - min;
    				else
    					maxInOrder[i] = maxInOrder[i - 1];
    				min = (prices[i] < min) ? prices[i] : min;
    			}
    			//maximum in reverse order
    			int[] maxInReverseOrder = new int[length];
    			maxInReverseOrder[length - 1] =0;
    			int max = prices[length - 1];
    			for(int i = length -2; i > -1; --i){
    				if(max - prices[i] > maxInReverseOrder[i + 1])
    					maxInReverseOrder[i] = max - prices[i];
    				else
    					maxInReverseOrder[i] = maxInReverseOrder[i + 1];
    				max = (prices[i] > max) ? prices[i] : max;
    			}
    			//find the maxProfit 
    			for(int k = 0; k < length; ++k)
    				maxProfit = (maxProfit < maxInOrder[k] + maxInReverseOrder[k]) ? maxInOrder[k] + maxInReverseOrder[k] : maxProfit;
    		}
    		return maxProfit;
        }  
    }

转载于:https://www.cnblogs.com/averillzheng/p/3771656.html