What is the best way to find the maximum product of two elements in an array?

Use a single linear pass to track the top two numbers or sort the array and take the last two elements; both ensure you maximize (nums[i]-1)*(nums[j]-1).

Can duplicate values affect the maximum product?

Yes, duplicates are valid if they appear at different indices. Always consider distinct positions when computing the product.

Is sorting necessary to solve this problem?

No, a linear scan for the top two numbers achieves the same result in O(n) time without extra sorting overhead.

What common mistakes should I avoid?

Remember to subtract 1 from each number before multiplying, and don't ignore array constraints that allow only valid indices.

How does the array plus sorting pattern apply here?

This pattern helps identify the largest elements efficiently, guiding toward a solution that maximizes the product without checking all pairs.

#1464

Easy

auto_awesome数组·排序

LeetCode 题解工作台

数组中两元素的最大乘积

给你一个整数数组 nums ，请你选择数组的两个不同下标 i 和 j ，使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。示例 1：输入： nums = [3,4,5,2] 输出： 12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），…

数组排序堆（优先队列）

题目描述

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。

请你计算并返回该式的最大值。

示例 1：

输入：nums = [3,4,5,2]
输出：12 
解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。

示例 2：

输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

示例 3：

输入：nums = [3,7]
输出：12

提示：

2 <= nums.length <= 500
1 <= nums[i] <= 10^3

lightbulb

解题思路

方法一：暴力枚举

双重循环，枚举所有的下标对，求出 $(nums[i]-1) \times (nums[j]-1)$ 的最大值。其中 $i \neq j$ 。

时间复杂度 $O(n^2)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        ans = 0
        for i, a in enumerate(nums):
            for b in nums[i + 1 :]:
                ans = max(ans, (a - 1) * (b - 1))
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for top elements quickly instead of testing every pair.
question_mark
Expect discussion of both sorting and linear scan methods.
question_mark
Clarify array constraints to justify linear-time optimization.

warning

常见陷阱

外企场景

error
Forgetting to subtract 1 from each number before multiplying.
error
Assuming elements can repeat without checking distinct indices.
error
Using nested loops unnecessarily when a linear scan suffices.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the maximum product of k elements in an array.
arrow_right_alt
Compute the maximum product modulo a large prime.
arrow_right_alt
Find the pair with the maximum product where elements must be consecutive.

help

常见问题

外企场景

继续练习

#1424 对角线遍历 II #1383 最大的团队表现值 #1353 最多可以参加的会议数目