Maximum Product Subarray

• Initialize max_product with the first element of nums.
• Iterate through the array with index i from 0 to n-1 (this will be the start of the subarray).
• Inside the first loop, initialize a current_product to 1.
• Start a nested loop with index j from i to n-1 (this will be the end of the subarray).
• In the inner loop, multiply current_product by nums[j].
• Compare current_product with max_product and update max_product if current_product is larger.
• After both loops complete, return max_product.

The brute-force method systematically considers every possible subarray. We can define a subarray by its starting and ending indices.

We use two nested loops. The outer loop, with index i, selects the start of the subarray. The inner loop, with index j, selects the end of the subarray.

For each subarray nums[i...j], we calculate its product. A running product can be maintained within the inner loop to avoid a third loop for calculation. The maximum product found across all subarrays is updated and stored. The initial maximum product can be set to the first element of the array to handle cases where all numbers are negative.

1class Solution {2    public int maxProduct(int[] nums) {3        if (nums.length == 0) {4            return 0;5        }6        int maxProduct = nums[0];7        for (int i = 0; i < nums.length; i++) {8            int currentProduct = 1;9            for (int j = i; j < nums.length; j++) {10                currentProduct *= nums[j];11                if (currentProduct > maxProduct) {12                    maxProduct = currentProduct;13                }14            }15        }16        return maxProduct;17    }18}

• Initialize max_product with the largest element in nums to handle edge cases.
• Initialize left_product = 1 and right_product = 1.
• Get the length of the array, n.
• Iterate with index i from 0 to n-1:
• If left_product is 0, reset it to 1. Then, update left_product by multiplying with nums[i].
• If right_product is 0, reset it to 1. Then, update right_product by multiplying with nums[n-1-i].
• Update max_product = max(max_product, left_product, right_product).
• Return max_product.

The core idea is that the maximum product subarray will not contain a zero (unless the max product is zero itself). Zeros act as separators, breaking the problem into smaller subproblems.

For a subarray without zeros, the maximum product is either the product of all its elements (if there's an even number of negatives) or the product of a subsegment that excludes one of the endmost negative numbers (if there's an odd number of negatives).

By calculating prefix products (from left to right) and suffix products (from right to left), we are guaranteed to find these maximums. The left-to-right pass will find the maximum product for subarrays with an odd number of negatives that ends at the right boundary. The right-to-left pass handles the case where it ends at the left boundary.

We can implement this in a single loop. We maintain two variables: left_product and right_product. In each iteration i, we update left_product with nums[i] and right_product with nums[n-1-i]. If either product becomes zero, we reset it to 1 to start a new subproblem.

1class Solution {2    public int maxProduct(int[] nums) {3        if (nums.length == 0) {4            return 0;5        }6        int maxProduct = nums[0];7        int leftProduct = 1;8        int rightProduct = 1;9        int n = nums.length;10 11        for (int i = 0; i < n; i++) {12            // Reset if product becomes 013            leftProduct = (leftProduct == 0 ? 1 : leftProduct) * nums[i];14            rightProduct = (rightProduct == 0 ? 1 : rightProduct) * nums[n - 1 - i];15            16            maxProduct = Math.max(maxProduct, Math.max(leftProduct, rightProduct));17        }18        return maxProduct;19    }20}

• If the array is empty, return 0.
• Initialize max_so_far, min_so_far, and result to the first element nums[0].
• Iterate through the array from the second element (i = 1 to n-1):
• Let current_num = nums[i].
• Store the old max_so_far in a temporary variable, say temp_max, as it's needed for the min_so_far calculation.
• The new max_so_far is the maximum of current_num, current_num * max_so_far, and current_num * min_so_far.
• The new min_so_far is the minimum of current_num, current_num * temp_max, and current_num * min_so_far.
• Update result = max(result, max_so_far).
• Return result.

The standard Kadane's algorithm for maximum sum subarray doesn't work directly because multiplying by a negative number can turn a maximum product into a minimum and vice-versa. For example, a large negative product, when multiplied by another negative number, can become the new maximum positive product.

To solve this, we maintain two variables at each step i:

1. max_so_far: the maximum product of a subarray ending at i.
2. min_so_far: the minimum product of a subarray ending at i.

When we process the next number num = nums[i], the new max_so_far can be one of three values: num itself (starting a new subarray), num * previous_max_so_far, or num * previous_min_so_far. The same logic applies to the new min_so_far. We also keep a global result variable that is updated with max_so_far at each step.

1class Solution {2    public int maxProduct(int[] nums) {3        if (nums.length == 0) {4            return 0;5        }6 7        int maxSoFar = nums[0];8        int minSoFar = nums[0];9        int result = maxSoFar;10 11        for (int i = 1; i < nums.length; i++) {12            int curr = nums[i];13            14            // Store the old maxSoFar because we need it to calculate the new minSoFar15            int tempMax = Math.max(curr, Math.max(maxSoFar * curr, minSoFar * curr));16            minSoFar = Math.min(curr, Math.min(maxSoFar * curr, minSoFar * curr));17 18            maxSoFar = tempMax;19 20            result = Math.max(maxSoFar, result);21        }22 23        return result;24    }25}