Maximum Product Subarray Explained — Kadane's Twist, Edge Cases & Interview Traps

public class MaxProductSubarrayBruteForce {

    /**
     * Brute-force O(n^2) approach — checks every possible subarray.
     * We show this FIRST so you feel the pain before seeing the fix.
     */
    public static int findMaxProductBruteForce(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;

        int overallMax = prices[0]; // start with first element, not Integer.MIN_VALUE
                                    // because all elements could be negative

        for (int start = 0; start < n; start++) {
            int runningProduct = 1;

            for (int end = start; end < n; end++) {
                runningProduct *= prices[end]; // extend subarray one step right

                // update global max after each extension
                overallMax = Math.max(overallMax, runningProduct);
            }
        }
        return overallMax;
    }

    public static void main(String[] args) {
        int[] stockMultipliers = {2, 3, -2, 4};
        System.out.println("Max product (brute force): "
            + findMaxProductBruteForce(stockMultipliers));
        // Subarrays: [2]=2, [2,3]=6, [2,3,-2]=-12, [2,3,-2,4]=-48
        //            [3]=3, [3,-2]=-6, [3,-2,4]=-24
        //            [-2]=-2, [-2,4]=-8
        //            [4]=4
        // Winner: [2, 3] = 6

        int[] withRescuingNegatives = {-2, -3, 4};
        System.out.println("Max product (brute force): "
            + findMaxProductBruteForce(withRescuingNegatives));
        // [-2,-3]=6, [-2,-3,4]=24  <-- two negatives rescue each other!
        // Winner: [-2, -3, 4] = 24
    }
}

public class MaxProductSubarrayOptimal {

    /**
     * O(n) time, O(1) space solution.
     * The key insight: track BOTH the max and min product ending at each index.
     * A negative number flips min into max and max into min — so we need both.
     */
    public static int findMaxProduct(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }

        // Initialize all three with the first element
        int maxProductSoFar = numbers[0];   // the answer we'll return
        int maxEndingHere   = numbers[0];   // best product of subarray ending at current index
        int minEndingHere   = numbers[0];   // worst product of subarray ending at current index

        for (int i = 1; i < numbers.length; i++) {
            int currentElement = numbers[i];

            // When we multiply by currentElement, max and min might swap.
            // We must compute both candidates BEFORE overwriting either variable.
            // That's why we save maxEndingHere in a temp variable first.
            int previousMax = maxEndingHere;

            // New maxEndingHere = best of:
            //   1) start fresh from currentElement
            //   2) extend the previous max subarray (positive * positive = bigger positive)
            //   3) extend the previous min subarray (negative * negative = positive)
            maxEndingHere = Math.max(
                currentElement,
                Math.max(previousMax * currentElement, minEndingHere * currentElement)
            );

            // New minEndingHere = worst of the same three candidates
            // (we want this because a future negative might flip it to a huge positive)
            minEndingHere = Math.min(
                currentElement,
                Math.min(previousMax * currentElement, minEndingHere * currentElement)
            );

            // Update global answer — max found anywhere in the array, not just at end
            maxProductSoFar = Math.max(maxProductSoFar, maxEndingHere);
        }

        return maxProductSoFar;
    }

    public static void main(String[] args) {
        // Test 1: Classic case — best subarray is [2, 3]
        int[] basicCase = {2, 3, -2, 4};
        System.out.println("Test 1 — [2, 3, -2, 4]:     " + findMaxProduct(basicCase));

        // Test 2: Two negatives rescue each other — best is [-2, -3, 4] = 24
        int[] twoNegatives = {-2, -3, 4};
        System.out.println("Test 2 — [-2, -3, 4]:        " + findMaxProduct(twoNegatives));

        // Test 3: Zero resets everything — best is [5, 6] = 30
        int[] withZero = {5, 6, 0, 3, 2};
        System.out.println("Test 3 — [5, 6, 0, 3, 2]:   " + findMaxProduct(withZero));

        // Test 4: All negatives — best is a single element [-1]
        int[] allNegatives = {-4, -3, -2};
        System.out.println("Test 4 — [-4, -3, -2]:       " + findMaxProduct(allNegatives));
        // [-4,-3]=12, but 12*-2=-24, so best full run is [-4,-3]=12
        // Wait — let's think: [-4]=−4, [-3]=−3, [-2]=−2, [-4,-3]=12, [-3,-2]=6, [-4,-3,-2]=−24
        // Winner: 12 ✓

        // Test 5: Single element
        int[] singleElement = {-7};
        System.out.println("Test 5 — [-7]:               " + findMaxProduct(singleElement));
    }
}

public class MaxProductTraceVisualizer {

    /**
     * Same algorithm as before, but with detailed tracing output
     * so you can see exactly how max and min evolve at each step.
     * Use this as a learning/debugging tool.
     */
    public static int findMaxProductWithTrace(int[] numbers) {
        int maxProductSoFar = numbers[0];
        int maxEndingHere   = numbers[0];
        int minEndingHere   = numbers[0];

        System.out.printf("%-5s %-8s %-14s %-14s %-16s%n",
            "i", "num[i]", "maxEndingHere", "minEndingHere", "maxProductSoFar");
        System.out.printf("%-5s %-8d %-14d %-14d %-16d%n",
            "init", numbers[0], maxEndingHere, minEndingHere, maxProductSoFar);

        for (int i = 1; i < numbers.length; i++) {
            int currentElement = numbers[i];
            int previousMax    = maxEndingHere;  // snapshot before mutation

            maxEndingHere = Math.max(
                currentElement,
                Math.max(previousMax * currentElement, minEndingHere * currentElement)
            );
            minEndingHere = Math.min(
                currentElement,
                Math.min(previousMax * currentElement, minEndingHere * currentElement)
            );
            maxProductSoFar = Math.max(maxProductSoFar, maxEndingHere);

            System.out.printf("%-5d %-8d %-14d %-14d %-16d%n",
                i, currentElement, maxEndingHere, minEndingHere, maxProductSoFar);
        }
        return maxProductSoFar;
    }

    public static void main(String[] args) {
        System.out.println("=== Tracing [-2, 3, -4] ===");
        int[] trickyArray = {-2, 3, -4};
        int result = findMaxProductWithTrace(trickyArray);
        System.out.println("\nFinal Answer: " + result);

        System.out.println("\n=== Tracing [1, -2, -3, 0, 7, -8, -2] ===");
        int[] mixedArray = {1, -2, -3, 0, 7, -8, -2};
        int result2 = findMaxProductWithTrace(mixedArray);
        System.out.println("\nFinal Answer: " + result2);
        // After 0 resets both to 0, we restart fresh
        // 7 * -8 * -2 = 112 is the winning subarray
    }
}

public class MaxProductTwoPassApproach {

    /**
     * Two-pass (forward + backward) approach.
     * Time: O(n), Space: O(1).
     *
     * Core idea: scan left-to-right accumulating products, reset on zero.
     * Then scan right-to-left doing the same. The max found in either
     * direction is the answer.
     *
     * Why it works: any subarray with an even number of negatives will
     * show a positive cumulative product in at least one direction.
     * The zero-reset ensures we never let a zero poison a subarray
     * on one side of it.
     */
    public static int findMaxProductTwoPass(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }

        int n = numbers.length;
        int maxProduct      = Integer.MIN_VALUE;
        int forwardProduct  = 1;
        int backwardProduct = 1;

        for (int i = 0; i < n; i++) {
            forwardProduct  *= numbers[i];           // left-to-right
            backwardProduct *= numbers[n - 1 - i];   // right-to-left (mirror index)

            // Update global max with both running products
            maxProduct = Math.max(maxProduct,
                         Math.max(forwardProduct, backwardProduct));

            // Reset to 1 (multiplicative identity) when we hit zero
            // This is equivalent to 'starting fresh' from the next element
            if (forwardProduct  == 0) forwardProduct  = 1;
            if (backwardProduct == 0) backwardProduct = 1;
        }

        return maxProduct;
    }

    public static void main(String[] args) {
        int[][] testCases = {
            {2, 3, -2, 4},
            {-2, -3, 4},
            {5, 6, 0, 3, 2},
            {-4, -3, -2},
            {-2, 3, -4},
            {1, -2, -3, 0, 7, -8, -2}
        };

        String[] labels = {
            "[2, 3, -2, 4]",
            "[-2, -3, 4]",
            "[5, 6, 0, 3, 2]",
            "[-4, -3, -2]",
            "[-2, 3, -4]",
            "[1, -2, -3, 0, 7, -8, -2]"
        };

        int[] expectedAnswers = {6, 24, 30, 12, 24, 112};

        for (int t = 0; t < testCases.length; t++) {
            int answer = findMaxProductTwoPass(testCases[t]);
            boolean correct = answer == expectedAnswers[t];
            System.out.printf("%-30s => %-5d %s%n",
                labels[t], answer, correct ? "✓" : "✗ (expected " + expectedAnswers[t] + ")");
        }
    }
}