漫画：去掉一个数，如何让剩余的数乘积最大？

2022-04-26 125

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 举个例子，给定如下数组：要删除哪个元素，才能使得剩余元素的乘积最大呢？

————— 第二天 —————

举个例子，给定如下数组：

要删除哪个元素，才能使得剩余元素的乘积最大呢？

显然应该删除元素2：

剩余元素的乘积 = 5 X 8 X 6 X9 X 7 = 15120

————————————

小灰把面试题目告诉给了大黄......

数组中哪个负数的绝对值最小呢？显然是元素-2：

我们删去元素-2，原本数组中的三个负数变成了两个，负负得正，而且保证了剩余元素的乘积最大。

数组中哪个非负元素最小呢？显然是元素3：

我们删去元素3，数组中剩余元素的乘积仍然是正数，而且绝对值最大。

数组中哪个负数元素的绝对值最大呢？显然是元素-9：

既然剩余元素的乘积无论如何都是负的，我们就索性删去绝对值最大的元素-9，使得剩余元素乘积的绝对值尽可能小。

总结一下，需要考虑的数组元素情况共有三种：

情况A：奇数个负数
情况B：偶数(包括0)个负数

子情况：没有非负数

public
static
int
 findRemovedIndex
(
int
[]
 array
){
// 1.统计负元素的个数
int
 negativeCount 
=
0
;
for
(
int
 i
=
0
;
 i
<
array
.
length
;
 i
++){
if
(
array
[
i
]
<
0
){
            negativeCount 
++;
}
}
// 2.根据不同情况，选择要删除的元素
int
 tempIndex 
=
0
;
if
((
negativeCount
&
1
)==
1
){
//情况A：负数个数是奇数
for
(
int
 i
=
1
;
 i
<
array
.
length
;
 i
++){
if
(
array
[
i
]
<
0
){
if
(
array
[
tempIndex
]>=
0
||
 array
[
i
]>
array
[
tempIndex
]){
                    tempIndex 
=
 i
;
}
}
}
return
 tempIndex
;
}
else
{
//情况B：负数个数是偶数
if
(
array
.
length 
==
 negativeCount
){
//子情况：所有元素都是负数
for
(
int
 i
=
1
;
 i
<
array
.
length
;
 i
++){
if
(
array
[
i
]
<
 array
[
tempIndex
]){
                    tempIndex 
=
 i
;
}
}
return
 tempIndex
;
};
for
(
int
 i
=
1
;
 i
<
array
.
length
;
 i
++){
if
(
array
[
i
]
>=
0
){
if
(
array
[
tempIndex
]<
0
||
 array
[
i
]<
array
[
tempIndex
]){
                    tempIndex 
=
 i
;
}
}
}
return
 tempIndex
;
}
}
public
static
void
 main
(
String
[]
 args
)
{
int
[]
 array1 
=
{-
4
,
3
,-
5
,-
7
,-
21
,
9
,-
1
,
5
,
6
};
int
 index 
=
 findRemovedIndex
(
array1
);
System
.
out
.
println
(
"删除元素下标："
+
 array1
[
index
]);
int
[]
 array2 
=
{
4
,
3
,
5
,-
7
,-
21
,
9
,-
1
,-
5
,
6
,
0
};
    index 
=
 findRemovedIndex
(
array2
);
System
.
out
.
println
(
"删除元素下标："
+
 array2
[
index
]);
int
[]
 array3 
=
{-
4
,-
3
,-
5
,-
7
,-
21
,-
9
,-
1
,-
8
};
    index 
=
 findRemovedIndex
(
array3
);
System
.
out
.
println
(
"删除元素下标："
+
 array3
[
index
]);
}