Java solution with just two traverses.


  • 37
    P

    Go from left to right and calculate max profit for each index (i). Go from right to left and calculate max profit for (i). Add max right profit for (i) and max left profit for (i-1) and check if it's max profit.

    public int maxProfit(int[] prices) {
    	if (prices == null || prices.length == 0) return 0;
    	int lenght = prices.length;
    	
    	int[] leftProfit = new int[lenght];
    	int leftMaxProfit = 0;
    	int leftMin = prices[0];
        for (int i=0; i<lenght; i++) {
        	if (prices[i] < leftMin) leftMin = prices[i];
        	if (prices[i] - leftMin > leftMaxProfit) leftMaxProfit = prices[i]-leftMin;
        	leftProfit[i] = leftMaxProfit;
        }
        
        int maxProfit = 0;
        int rightMaxProfit = 0;
    	int rightMax = prices[lenght-1];
    	for (int i=lenght-1; i>=0; i--) {
        	if (prices[i] > rightMax) rightMax = prices[i];
        	if (rightMax - prices[i] > rightMaxProfit) rightMaxProfit = rightMax - prices[i];
        	int currentProfit = rightMaxProfit + (i>0 ? leftProfit[i-1] : 0);
        	if (currentProfit > maxProfit) {
        		maxProfit = currentProfit;
        	}
        }
    	
        return maxProfit;
    }

  • 0
    L

    Could anyone tell me why "if (prices[i] < leftMin) leftMin = prices[i];" is faster than "leftMin = Math.min(leftMin, price[i])" ?


  • 0

    I think it's the same.


  • 1
    X

    I have the same idea with you.
    But I transform the prices array as price differences, so that it becomes similar to the problem 53 Maximum Subarray.

    Here is my code.

    int Solution::maxProfit_split(vector<int>& prices) {
        int n = prices.size();
        if (n < 2) {
            return 0;
        }
    
        int current_profit;
    
        current_profit = 0;
        vector<int> max_profit_left(n);
        max_profit_left.front() = 0;
        for (int i = 1; i < n; ++i) {  // max profit on interval [0, i]
            current_profit = max(current_profit, 0);
            current_profit += prices[i] - prices[i - 1];
            max_profit_left[i] = max(max_profit_left[i - 1], current_profit);
        }
    
        current_profit = 0;
        vector<int> max_profit_right(n);
        max_profit_right.back() = 0;
        for (int i = n - 2; i >= 0; --i) {    // max profit on interval [i, n - 1]
            current_profit = max(current_profit, 0);
            current_profit += prices[i + 1] - prices[i];
            max_profit_right[i] = max(max_profit_right[i + 1], current_profit);
        }
    
        int max_profit = 0;
        for (int i = 2; i <= n - 2; ++i) {  // two transactions
            max_profit = max(max_profit, max_profit_left[i - 1] + max_profit_right[i]);
        }
        max_profit = max(max_profit, max_profit_left[n - 1]);  // only one transaction
    
        return max_profit;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.