34. Maximum Product of Two Elements in an Array

Given an array of integers nums, choose two different indices i and j such that (nums[i]-1) * (nums[j]-1) is maximized. Return the maximum value.

Input: An integer array nums of length n.

Output: Integer — maximum value of (nums[i]-1)*(nums[j]-1).

Examples

Input: [3,4,5,2]
Output: 12
Explanation: Max two values: 5 and 4. (5-1)*(4-1) = 4*3 = 12.

Input: [1,5,4,5]
Output: 16
Explanation: Max two values: 5 and 5. (5-1)*(5-1) = 4*4 = 16.

Input: [3,7]
Output: 12
Explanation: Only two elements. (7-1)*(3-1) = 6*2 = 12.

Constraints

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

Asked by