O(n) solution without using DP. Using Divide and Conquer technique


  • 0
    V

    I know the problem tag says it is a DP problem but this can also be solved using divide and conquer approach. The Idea is to divide the array in two halves and call it recursively. recursive method will return 3 values maxProfit, minPrice and maxPrice. For each iteration max profit will be max of maxProfit of each halves compared with the difference of max of right half and min of left half. Following is the code

    public int maxProfit(int[] prices) {
            return prices.length > 0 ? helper(prices,0,prices.length -1)[0] : 0;
        }
        /**
         * index 0 is max profit, index 1 is max price in the range and index 2 is min price in the range.
         */
        private int[] helper(int[] prices, int i, int j){
            int[] result = {0,prices[i],prices[j]}; // base case 
            if(i == j) return result;
            int m = i + (j - i) / 2 ;
            int[] left = helper(prices,i,m); // left half
            int[] right = helper(prices,m+1,j); // right half
            result[0] = Math.max(left[0],Math.max(right[0],right[1] - left[2]));
            result[1] = Math.max(left[1],right[1]);
            result[2] = Math.min(left[2],right[2]);
            return result;
        }

Log in to reply
 

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