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