Solution by Dr.LGY


  • 0
    D

    Solution

    There is no overlap between two transactions, so we can divide the array into two section by a split point, and then find the maximum profit of the left and right side, respectively.

    If we want to find the maximum profit of an array, we need to find out the maximum difference (which will be the maximum profit) between two numbers in the array. Besides, the second number (selling price) must be larger than the first one (buying price).

    After finding out all the maximum profit of the left and right side of each point, find the maximum sum of left maximum profit and right maximum profit of each split point (which is the answer).

    In formal terms, we can find out and save leftMaxProfit[i] and rightMaxProfit[i] for each i firstly, and then we need to find max ( leftMaxProfit[i] + rightMaxProfit[i] ) for each i.
    ____________________________________________________________________

    Approach #1 (Brute Force) [Time Limit Exceeded]

    Java

    class Solution {
         public int maxProfit(int[] prices) {
        	int maxLeft = 0;
        	int []leftProfit = new int[prices.length];
            for (int i = 0; i < prices.length; i++) {
            	for (int j = 0; j < i; j++) {
            		if (prices[i] > prices[j]) {
            			if (prices[i] - prices[j] > maxLeft) {
            				maxLeft = prices[i] - prices[j]; 
            			}
            		}
            	}
            	leftProfit[i] = maxLeft;
            }
             
            int maxRight = 0;
            int []rightProfit = new int[prices.length];
            for (int i = prices.length - 1; i >= 0; i--)  {
            	for (int j = prices.length - 1; j > i; j--) {
            		if (prices[j] > prices[i]) {
            			if(prices[j] - prices[i] > maxRight) {
            				maxRight = prices[j] - prices[i]; 
            			}
            		}
            	}
            	rightProfit[i] = maxRight;
            }
             
            int maxProfit = 0;
            for (int i = 0; i < prices.length; i++) {
            	if (leftProfit[i] + rightProfit[i] > maxProfit) {
            		maxProfit = leftProfit[i] + rightProfit[i];
            	}
            }
            return maxProfit;
        }
    } 
    

    Complexity Analysis

    • Time complexity : O(n^2). The first two Loops run n*(n-1)/2 times each, while the third runs n times.
    • Space complexity : O(n). O(n) space for leftProfit and rightProfit.

    Approach #2 (One Pass) [Accepted]

    Algorithm
    Say the given array is:
    [7, 1, 5, 3, 6, 4]
    If we plot the numbers of the given array on a graph and divide it into two part by split point, we get:
    0_1517553623102_aa.png
    Firstly, we need to divide the graph into two section by one split point, and then find the maximum interest of left side and right side.

    In order to find the maximum interest of left side, we need to find the largest peak following the smallest valley from the first point on and end up in the split point, and we can maintain two variables - minprice and maxLeftProfit corresponding to the smallest valley and maximum profit of left side (maximum difference between selling price and minprice) obtained so far respectively.

    But on the right side, we need to find the smallest valley following the largest peak from the last point on and end up in the split point, and we can maintain two variables - maxprice and maxRightProfit corresponding to the largest peak and maximum profit of right side (maximum difference between buying price and maxprice) obtained so far respectively.

    java

    class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length <= 1) return 0;
            int maxLeft = 0;
        	int minPrice = prices[0];
        	int []leftProfit = new int[prices.length];
            for (int i = 0; i < prices.length; i++) {
            	if (minPrice > prices[i]) 
            		minPrice = prices[i];
            	if (prices[i] - minPrice > maxLeft) 
            		maxLeft = prices[i] - minPrice;
            	leftProfit[i] = maxLeft;
            }
            int maxRight = 0;
            int []rightProfit = new int[prices.length];
            int maxPrice = prices[prices.length - 1];
            for (int i = prices.length - 1; i >= 0; i--)  {
            	if (maxPrice < prices[i]) 
                            maxPrice = prices[i];
            	if (maxPrice - prices[i] > maxRight) 
            		maxRight = maxPrice - prices[i];
            	rightProfit[i] = maxRight; 
            }
            int maxProfit = 0;
            for (int i = 0; i < prices.length; i++) {
            	if (leftProfit[i] + rightProfit[i] > maxProfit) 
            		maxProfit = leftProfit[i] + rightProfit[i];
            }
            return maxProfit;
        
        }
    }
    

    Complexity Analysis

    • Time complexity : O(n). Only three single pass is needed.
    • Space complexity : O(n). Still O(n) space for leftProfit and rightProfit.

  • 0
    D

    @Dr.LGY If you feel it is easy-understanding, please give me a vote, I will be deeply grateful. And if there are some wrong or doubt, welcome to your reply, I will try my best to answer for you, thank you every one.


Log in to reply
 

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