To solve this problem, we need to find the maximum product of two distinct elements in an array, where each element is reduced by 1 before multiplication. The solution must account for both positive and negative numbers, as the product of two negative numbers can be larger than the product of the largest positive numbers.

Approach

The key insight here is to consider two scenarios:

1. The product of the two largest elements (after subtracting 1) — this handles positive numbers.
2. The product of the two smallest elements (after subtracting 1) — this handles cases where two negative numbers yield a large positive product.

To implement this:

1. Track the two largest values (max1, max2) and the two smallest values (min1, min2) in the array.
2. Compute the product for both scenarios and return the maximum of the two.

Solution Code

def max_product(nums):
    max1 = max2 = float('-inf')
    min1 = min2 = float('inf')

    for num in nums:
        # Update the two largest values
        if num > max1:
            max2 = max1
            max1 = num
        elif num > max2:
            max2 = num

        # Update the two smallest values
        if num < min1:
            min2 = min1
            min1 = num
        elif num < min2:
            min2 = num

    # Calculate both possible products
    product_largest = (max1 - 1) * (max2 - 1)
    product_smallest = (min1 - 1) * (min2 - 1)

    return max(product_largest, product_smallest)

Explanation

1. Tracking Extremes: We iterate through the array once to find the two largest and two smallest elements. This is done in O(n) time complexity, where n is the number of elements in the array.
2. Product Calculation: We compute the product of the two largest elements (after subtracting 1) and the product of the two smallest elements (after subtracting 1). The maximum of these two products gives the desired result.

This approach efficiently handles all edge cases, including negative numbers, duplicates, and small arrays, ensuring optimal performance and correctness.

Example: For the array [-3, -4, 0], the two smallest elements are -4 and -3, so their product after subtraction is (-4-1)*(-3-1) = (-5)*(-4) = 20, which is larger than the product of the largest elements (0 and -3 → (0-1)*(-3-1) =4). Thus, the result is 20.

This solution is optimal and works for all test cases. It runs in O(n) time and uses O(1) additional space.

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