Example: Maximum Product Subarray - Optimized in Java

// Maximum Product Subarray - Optimized
import java.util.Scanner; // Included as per template, though not strictly used in this example.

// Main class containing the entry point of the program
public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        // int[] nums = {-2, 0, -1}; // Expected 0
        // int[] nums = {-2, -3, -1}; // Expected 6

        if (nums == null || nums.length == 0) {
            System.out.println("The array is empty. Max product: 0");
            return;
        }

        // Step 1: Initialize variables
        // overall_max: Stores the maximum product found across all subarrays
        // max_so_far: Stores the maximum product ending at the current position
        // min_so_far: Stores the minimum product ending at the current position (important for negatives)
        long overall_max = nums[0];
        long max_so_far = nums[0];
        long min_so_far = nums[0];

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

            // Step 3: If current_num is negative, swap max_so_far and min_so_far
            // This is because multiplying a negative number will reverse their roles:
            // max_so_far * current_num would become the new min_so_far
            // min_so_far * current_num would become the new max_so_far
            if (current_num < 0) {
                long temp = max_so_far;
                max_so_far = min_so_far;
                min_so_far = temp;
            }

            // Step 4: Update max_so_far and min_so_far for the current position
            // max_so_far will be the maximum of:
            //   1. current_num itself (starting a new subarray)
            //   2. product of max_so_far from previous step and current_num
            max_so_far = Math.max(current_num, max_so_far * current_num);

            // min_so_far will be the minimum of:
            //   1. current_num itself (starting a new subarray)
            //   2. product of min_so_far from previous step and current_num
            min_so_far = Math.min(current_num, min_so_far * current_num);

            // Step 5: Update the overall_max with the maximum product found so far
            overall_max = Math.max(overall_max, max_so_far);
        }

        System.out.println("Maximum product subarray (Optimized): " + overall_max);
    }
}