Example: Maximum Product Subarray - Dynamic Programming in Java

// Maximum Product Subarray - Dynamic Programming
import java.util.Arrays;

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] nums1 = {2, 3, -2, 4};
        System.out.println("Array: " + Arrays.toString(nums1) + ", Max Product: " + maxProductDP(nums1)); // Expected: 6

        int[] nums2 = {-2, 0, -1};
        System.out.println("Array: " + Arrays.toString(nums2) + ", Max Product: " + maxProductDP(nums2)); // Expected: 0

        int[] nums3 = {-2, 3, -4};
        System.out.println("Array: " + Arrays.toString(nums3) + ", Max Product: " + maxProductDP(nums3)); // Expected: 24

        int[] nums4 = {0, 2};
        System.out.println("Array: " + Arrays.toString(nums4) + ", Max Product: " + maxProductDP(nums4)); // Expected: 2

        int[] nums5 = {-1, -2, -9, -6};
        System.out.println("Array: " + Arrays.toString(nums5) + ", Max Product: " + maxProductDP(nums5)); // Expected: 108
    }

    public static int maxProductDP(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        // Step 1: Initialize variables
        int max_so_far = nums[0]; // Maximum product ending at the current position
        int min_so_far = nums[0]; // Minimum product ending at the current position
        int result = nums[0];     // Overall maximum product found so far

        // Step 2: Iterate through the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];

            // Step 3: Store max_so_far before it's potentially updated
            // This is crucial because the new min_so_far might depend on the old max_so_far
            int temp_max = Math.max(current, Math.max(max_so_far * current, min_so_far * current));
            min_so_far = Math.min(current, Math.min(max_so_far * current, min_so_far * current));

            max_so_far = temp_max; // Update max_so_far with the value calculated using old max_so_far and min_so_far

            // Step 4: Update the overall result
            result = Math.max(result, max_so_far);
        }

        return result;
    }
}