To solve this problem, we need to find the maximum product of two distinct elements in an array after reducing each element by one. The key insight here is to consider both the largest and smallest elements in the array, as the product of two large positive numbers or two small negative numbers can yield the maximum result.

Approach

1. Identify the Two Largest Elements: The product of the two largest elements (after subtracting one) is a candidate for the maximum value.
2. Identify the Two Smallest Elements: The product of the two smallest elements (after subtracting one) is another candidate, especially if both are negative (since their product will be positive and potentially large).
3. Compute and Compare: Calculate the product for both candidates and return the maximum value.

Solution Code

def max_product(nums):
    # Find the two largest numbers
    max1 = max2 = float('-inf')
    for num in nums:
        if num > max1:
            max2 = max1
            max1 = num
        elif num > max2:
            max2 = num

    # Find the two smallest numbers
    min1 = min2 = float('inf')
    for num in nums:
        if num < min1:
            min2 = min1
            min1 = num
        elif num < min2:
            min2 = num

    # Calculate the two possible maximum products
    option1 = (max1 - 1) * (max2 - 1)
    option2 = (min1 - 1) * (min2 - 1)

    return max(option1, option2)

Explanation

1. Finding Two Largest Elements: We iterate through the array and keep track of the top two largest elements. This helps us compute the product of the two largest values (after subtracting one).
2. Finding Two Smallest Elements: Similarly, we iterate through the array to track the bottom two smallest elements. This is crucial because the product of two negative numbers (after subtraction) can be larger than the product of positive numbers.
3. Result Calculation: We compute the product for both the largest and smallest pairs (after subtracting one) and return the maximum of these two products. This ensures we cover all possible cases for the maximum product.

This approach efficiently finds the required values in linear time, O(n), making it suitable for large arrays. The solution handles all edge cases, including arrays with all negative numbers, all positive numbers, and mixed values.

Example Test Cases:

• For input [3,4,5], the result is (5-1)*(4-1)=12.
• For input [-5,-4,1], the result is (-5-1)*(-4-1)=30.
• For input [-100,-99,100], the result is (-100-1)*(-99-1)=10100.

This solution is optimal and covers all possible scenarios to find the maximum product.

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