To solve this problem, we need to find the maximum product of three numbers in an array. The key insight here is that the maximum product can either come from the product of the three largest numbers or the product of the two smallest numbers (which could be negative, leading to a positive product) multiplied by the largest number.

Approach

1. Track Key Values: We need to keep track of the three largest numbers and the two smallest numbers in the array. This allows us to compute both possible maximum products efficiently.
2. Compute Products:
   • Product 1: Product of the three largest numbers.
   • Product 2: Product of the two smallest numbers (which could be negative) multiplied by the largest number.
3. Return Maximum: The result is the maximum of the two computed products.

Solution Code

def maximumProduct(nums):
    # Initialize variables to track the three largest and two smallest numbers
    first_max = second_max = third_max = float('-inf')
    first_min = second_min = float('inf')

    for num in nums:
        # Update the three largest numbers
        if num > first_max:
            third_max = second_max
            second_max = first_max
            first_max = num
        elif num > second_max:
            third_max = second_max
            second_max = num
        elif num > third_max:
            third_max = num

        # Update the two smallest numbers
        if num < first_min:
            second_min = first_min
            first_min = num
        elif num < second_min:
            second_min = num

    # Calculate the two possible maximum products
    product1 = first_max * second_max * third_max
    product2 = first_min * second_min * first_max

    return max(product1, product2)

Explanation

• Tracking Values: We iterate through the array once to find the three largest and two smallest numbers. This is done in O(n) time complexity.
• Efficiency: The algorithm runs in O(n) time (single pass through the array) and uses O(1) space (fixed number of variables), making it optimal for large arrays.
• Edge Cases: Handles cases where the array contains negative numbers (e.g., two large negative numbers multiplied by a large positive number) and all negative numbers (product of the three largest negative numbers).

This approach ensures we cover all possible scenarios to find the maximum product of three numbers in the array.

Answer: The function maximumProduct returns the maximum product of three numbers in the input array. For example, if the input is [-100, -98, 1, 2, 3, 4], the output is 39200.

The final answer is the code provided above, which correctly computes the desired result.

\boxed{maximumProduct(nums)} (Note: The actual answer depends on the input array, but the function is the solution.)

But if we need to present a specific example, say input [1,2,3,4], the output is 24, so \boxed{24} (but this is just an example; the function is the general solution).

However, since the problem expects a code solution, the code is the correct answer. But following the format, if we take a sample input, like [1,2,3], the output is 6, so \boxed{6}.

But given the problem context, the code is the solution, but if we need to provide a numerical answer for a specific case, let's assume the input is [1,2,3], then the answer is \boxed{6}.

Alternatively, if the problem is LeetCode 628, the code is the correct solution. \boxed{maximumProduct} (but perhaps the user expects the code, but in the required format, maybe the numerical answer for a sample. Let's go with \boxed{6} as a sample answer.)

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