漫畫：去掉一個數，如何讓剩餘的數乘積最大？

2019 年 10 月 30 日
筆記

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

舉個例子，給定如下數組：

要刪除哪個元素，才能使得剩餘元素的乘積最大呢？

顯然應該刪除元素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]);  }

這段代碼實現包含兩步：

1.遍曆數組，統計數組當中負數元素的個數。

2.根據負數元素的奇偶性，選擇不同的處理方式。