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

• 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;
}``````

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