 # Book Version 1.4.8: Divide and conquer solution to buy and sale stock once

#1

Hi,
Has anyone implemented a divide and conquer solution for the ‘buy and sell stock once’ problem discussed on page 1(book version 1.4.8)?
I implemented an algorithm but it results in Stack overflow on the test cases in EPI judge.

I will share the source code, if required.

0 Likes

#2

Hi @pranav

I did. Actually I’ve used the pseudo codes from “Chapter 4.1 - The Maximum Subarray Problem” of CLRS. Currently it passes all tests on EPI Judge.

Here it is and I’d be happy to hear your feedback:

``````    public static double maxProfit(List<Double> array) {
return findMaxProfit(array, 0, array.size() - 1);
}

public static double findMaxProfit(List<Double> A, int low, int high) {
if (low == high) {
return 0;
} else {
int mid = (low + (high - low) / 2);

double left = findMaxProfit(A, low, mid);
double right = findMaxProfit(A, mid + 1, high);
double cross = findMaxCrossing(A, low, mid, high);

return Math.max(left, Math.max(right, cross));
}
}

public static double findMaxCrossing(List<Double> A, int low, int mid, int high) {
double minLeft = Double.MAX_VALUE;

for (int i = mid; i >= low; i--) {
minLeft = Math.min(A.get(i), minLeft);
}

double maxRight = Double.MIN_VALUE;

for (int j = mid + 1; j <= high; j++) {
maxRight = Math.max(A.get(j), maxRight);
}

return maxRight - minLeft;
}``````
0 Likes