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

赞



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





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



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


显然应该删除元素2：



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




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




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







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



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






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



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








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



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



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


  • 情况A：奇数个负数

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

    • 子情况：没有非负数



  1. public static int findRemovedIndex(int[] array){
  2.     // 1.统计负元素的个数
  3.     int negativeCount = 0;
  4.     for(int i=0; i<array.length; i++){
  5.         if(array[i] < 0){
  6.             negativeCount ++;
  7.         }
  8.     }
  9.     // 2.根据不同情况，选择要删除的元素
  10.     int tempIndex = 0;
  11.     if((negativeCount&1)==1){
  12.         //情况A：负数个数是奇数
  13.         for(int i=1; i<array.length; i++){
  14.             if(array[i] < 0){
  15.                 if(array[tempIndex]>=0 || array[i]>array[tempIndex]){
  16.                     tempIndex = i;
  17.                 }
  18.             }
  19.         }
  20.         return tempIndex;
  21.     } else {
  22.         //情况B：负数个数是偶数
  23.         if(array.length == negativeCount){
  24.             //子情况：所有元素都是负数
  25.             for(int i=1; i<array.length; i++){
  26.                 if(array[i] < array[tempIndex]){
  27.                     tempIndex = i;
  28.                 }
  29.             }
  30.             return tempIndex;
  31.         };
  32.         for(int i=1; i<array.length; i++){
  33.             if(array[i] >= 0){
  34.                 if(array[tempIndex]<0 || array[i]<array[tempIndex]){
  35.                     tempIndex = i;
  36.                 }
  37.             }
  38.         }
  39.         return tempIndex;
  40.     }
  41. }


  3. public static void main(String[] args) {
  4.     int[] array1 = {-4,3,-5,-7,-21,9,-1,5,6};
  5.     int index = findRemovedIndex(array1);
  6.     System.out.println("删除元素下标："+ array1[index]);

  8.     int[] array2 = {4,3,5,-7,-21,9,-1,-5,6,0};
  9.     index = findRemovedIndex(array2);
  10.     System.out.println("删除元素下标："+ array2[index]);

  12.     int[] array3 = {-4,-3,-5,-7,-21,-9,-1,-8};
  13.     index = findRemovedIndex(array3);
  14.     System.out.println("删除元素下标："+ array3[index]);
  15. }


这段代码实现包含两步：

1.遍历数组，统计数组当中负数元素的个数。

2.根据负数元素的奇偶性，选择不同的处理方式。






上面这个数组是典型的情况B，即负数个数是偶数的情况。那么要想让剩余元素乘积最大，我们只要删除最小的非负元素，也就是删除元素0即可：





—————END—————




喜欢本文的朋友，欢迎关注公众号 程序员小灰，收看更多精彩内容



欢迎长按二维码关注 小灰学英语，你所学到的不只是英语！



给个[在看]，是对小灰最大的支持！