Java All 3 Solutions (BruteForce-timeout, DP-3ms & Divide&Conquer-4ms)

• ``````public class Solution {

public int maxProfitBruteForce(int[] prices) {
int max = 0;
for(int i=0; i<prices.length; i++)
for(int j=i+1; j<prices.length; j++)
max = prices[j]-prices[i] > max ? prices[j]-prices[i] : max;
return max;
}

public int maxProfitRec(int[] prices, int i, int j) {
if(i==j)
return 0;
int mid = (i+j) / 2;
int leftProfit = maxProfitRec(prices, i, mid);
int rightProfit = maxProfitRec(prices, mid+1, j);
int subMax = Math.max(leftProfit,rightProfit);

int leftMin = prices[i];
for(int k=i+1; k<=mid; k++)
leftMin = prices[k] < leftMin ? prices[k] : leftMin;

int rightMax = prices[mid+1];
for(int k=mid+2; k<=j; k++)
rightMax = prices[k] > rightMax ? prices[k] : rightMax;

int crossMax = Math.max(0,rightMax-leftMin);

return Math.max(subMax,crossMax);
}

public int maxProfitDp(int[] prices) {
int buy = prices[0];
int max = 0;
for(int i=1; i<prices.length; i++) {
max = prices[i]-buy > max ? prices[i]-buy : max;
if(prices[i]<buy)
buy = prices[i];
}
return max;
}

public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
// return maxProfitBruteForce(prices);
// return maxProfitRec(prices,0,prices.length-1);
return maxProfitDp(prices);
}

}``````

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