To solve the Maximum Product Subarray problem (a classic dynamic programming problem), we need to find the contiguous subarray with the largest product in a given integer array. The challenge lies in handling negative numbers, which can flip the sign of the product—turning a small negative product into a large positive one (and vice versa).

Problem Statement

Given an integer array nums, return the maximum product of any non-empty contiguous subarray.

Approach

The key insight here is to track both the maximum and minimum product ending at the current index (since a negative number can flip the sign of the product). Here's the step-by-step approach:

1. Initialization:

   • max_so_far: The maximum product ending at the current index.
   • min_so_far: The minimum product ending at the current index (critical for handling negatives).
   • result: The overall maximum product found so far.
   • Start with all three variables set to the first element of the array.

2. Transition: For each subsequent element:

   • Compute the new maximum product as the maximum of three values: a) The element itself (starting a new subarray here). b) The product of the current element and max_so_far (extending the previous max subarray). c) The product of the current element and min_so_far (extending the previous min subarray—since a negative min can become positive when multiplied by another negative).
   • Compute the new minimum product similarly (using the minimum of the three values).
   • Update result if the new max_so_far is larger than the current result.

3. Result: The final value of result is the maximum product subarray.

Solution Code

def maxProduct(nums):
    if not nums:
        return 0

    max_so_far = min_so_far = result = nums[0]

    for num in nums[1:]:
        # Calculate new max and min using previous values (store in temp to avoid overwriting)
        temp_max = max(num, max_so_far * num, min_so_far * num)
        temp_min = min(num, max_so_far * num, min_so_far * num)

        max_so_far, min_so_far = temp_max, temp_min
        result = max(result, max_so_far)

    return result

Explanation

Let’s break down the solution with examples:

Example 1: nums = [2,3,-2,4]

• Index 0: max=2, min=2, result=2.
• Index1: max=6 (2*3), min=3, result=6.
• Index2: max=-2 (start new subarray), min=-12 (6*-2), result=6.
• Index3: max=4 (start new subarray), min=-48 (-2*4), result=6.

Final result: 6 (subarray [2,3]).

Example2: nums = [-2,-3,-4]

• Index0: max=-1, min=-1, result=-1.
• Index1: max=2 (-1*-2), min=-2, result=2.
• Index2: max=18 (-2-9), min=-18 (2-9), result=18.
• Index3: max=108 (-18-6), min=-108 (18-6), result=108.

Final result: 108 (subarray [-1,-2,-9,-6]).

Complexity

• Time: O(n) (one pass through the array).
• Space: O(1) (only a few variables used, no extra space for DP arrays).

This approach efficiently handles all edge cases, including negative numbers and zeros, making it the optimal solution for this problem.

作者声明:本文包含人工智能生成内容。