Array
Sorting
Heap (Priority Queue)
Description
Given the array of integers nums
, you will choose two different indices i
and j
of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1)
.
Example 1:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.
Example 2:
Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
Example 3:
Input: nums = [3,7]
Output: 12
Constraints:
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
Solutions
Solution 1
Python3 Java C++ Go TypeScript Rust PHP C
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
1
2
3
4
5
6
7
8
9
10
11
12 class Solution {
public int maxProduct ( int [] nums ) {
int ans = 0 ;
int n = nums . length ;
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
ans = Math . max ( ans , ( nums [ i ] - 1 ) * ( nums [ j ] - 1 ));
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution {
public :
int maxProduct ( vector < int >& nums ) {
int ans = 0 ;
int n = nums . size ();
for ( int i = 0 ; i < n ; ++ i ) {
for ( int j = i + 1 ; j < n ; ++ j ) {
ans = max ( ans , ( nums [ i ] - 1 ) * ( nums [ j ] - 1 ));
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12 func maxProduct ( nums [] int ) int {
ans := 0
for i , a := range nums {
for _ , b := range nums [ i + 1 :] {
t := ( a - 1 ) * ( b - 1 )
if ans < t {
ans = t
}
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13 function maxProduct ( nums : number []) : number {
const n = nums . length ;
for ( let i = 0 ; i < 2 ; i ++ ) {
let maxIdx = i ;
for ( let j = i + 1 ; j < n ; j ++ ) {
if ( nums [ j ] > nums [ maxIdx ]) {
maxIdx = j ;
}
}
[ nums [ i ], nums [ maxIdx ]] = [ nums [ maxIdx ], nums [ i ]];
}
return ( nums [ 0 ] - 1 ) * ( nums [ 1 ] - 1 );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 impl Solution {
pub fn max_product ( nums : Vec < i32 > ) -> i32 {
let mut max = 0 ;
let mut submax = 0 ;
for & num in nums . iter () {
if num > max {
submax = max ;
max = num ;
} else if num > submax {
submax = num ;
}
}
( max - 1 ) * ( submax - 1 )
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function maxProduct($nums) {
$max = 0;
$submax = 0;
for ($i = 0; $i < count($nums); $i++) {
if ($nums[$i] > $max) {
$submax = $max;
$max = $nums[$i];
} elseif ($nums[$i] > $submax) {
$submax = $nums[$i];
}
}
return ($max - 1) * ($submax - 1);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14 int maxProduct ( int * nums , int numsSize ) {
int max = 0 ;
int submax = 0 ;
for ( int i = 0 ; i < numsSize ; i ++ ) {
int num = nums [ i ];
if ( num > max ) {
submax = max ;
max = num ;
} else if ( num > submax ) {
submax = num ;
}
}
return ( max - 1 ) * ( submax - 1 );
}
Solution 2
Solution 3
Python3 Java C++ Go
class Solution :
def maxProduct ( self , nums : List [ int ]) -> int :
a = b = 0
for v in nums :
if v > a :
a , b = v , a
elif v > b :
b = v
return ( a - 1 ) * ( b - 1 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution {
public int maxProduct ( int [] nums ) {
int a = 0 , b = 0 ;
for ( int v : nums ) {
if ( v > a ) {
b = a ;
a = v ;
} else if ( v > b ) {
b = v ;
}
}
return ( a - 1 ) * ( b - 1 );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution {
public :
int maxProduct ( vector < int >& nums ) {
int a = 0 , b = 0 ;
for ( int v : nums ) {
if ( v > a ) {
b = a ;
a = v ;
} else if ( v > b ) {
b = v ;
}
}
return ( a - 1 ) * ( b - 1 );
}
};
func maxProduct ( nums [] int ) int {
a , b := 0 , 0
for _ , v := range nums {
if v > a {
b , a = a , v
} else if v > b {
b = v
}
}
return ( a - 1 ) * ( b - 1 )
}