TomWang

有個題目是這樣:

 

---

寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
請回傳一個陣列裡面相鄰互乘的最大整數值
例如: [2 , -7 , 0  , 2 , 3 , 8 , -6 , 5]
就是 2 * 3 * 8 = 48
再一個例子: [-2 , 0 , 3 , 5 , -7]
就是 3 * 5 = 15

---

這題有個盲點，當初面試題目是只有相鄰兩個數可以相乘?還是可以無限相乘?
因為例子的關係，變成可以無限相乘
但如果題目真的是只有相鄰兩個數相乘，那我想暴力解的解法大概就會是每個數跟下一個數相乘，然後判斷是否有比目前最大值大，這樣時間複雜度是O(n)
優化也會是這樣...
所以這裡假設是可以無限相乘的情況來描述怎麼解決題目好了

這裡先將數字分三種類型
1.正數:正數相乘只會相等或更大，而不會更小
2.負數:在都沒0的情況之下，奇數個負數相成會是負數，偶數的話就會變正數
3.0:不管數字多大或多小，乘０都會變０

我對這題目的想法是這樣:
1.以0來把陣列分成多個小組
2.如果一個小組沒有負數或有偶數個負數，就直接全部相乘。如果是奇數就得嘗試各種分得更細的算法
3.將前面各小組的結果一起比較，取出最大值

以下是我寫的CODE:

 

public class MaxNumberService {
          public Integer getMaxNumber(int[] numbers){
               int startIndex = 0;
               Integer max=numbers[0];
               Integer countNe=0;
               Integer tempMax=1;
               for (int i = 0; i < numbers.length; i++) {
                    if (numbers[i] == 0){
                         if(i==startIndex){
                              //如果第一個為0或連續0
                              tempMax=numbers[i];
                         }
                         else if(countNe%2==0){
                              //如果負數個數為偶數，且都沒有0，那麼相乘只會更大或不變而不會更小，這時不用做任何判斷直接全部相乘即是最大值
                              for(int j=startIndex;j0?tempMax:0;
                         }
                         max=tempMax>max?tempMax:max;
                         startIndex=i+1;
                         countNe=0;
                         tempMax=1;
                    }else if(numbers[i]<0){
                         countNe++;
                    }
               }
               //做最後處理
               if (startIndexmax?tempMax:max;
               }
               return max;
          }
          private Integer refine(int[] array,int startIndex,int endIndex){
               Integer max=array[startIndex];
               Integer tempMax;
               for (int i = startIndex; i <= endIndex; i++) {
                    tempMax=1;
                    for (int j = i; j <= endIndex; j++) {
                         tempMax*=array[j];
                         max=tempMax>max?tempMax:max;
                    }
               }
               return max;
          }
     }
}

我想時間複雜度上可以這樣描述：
總數是n，m是用0分組後，有奇數個負數的小組中，數字最多個的個數。
時間複雜度為O(n) or O(m^2)
有可能n=m
要直接當O(n^2)也OK

這樣一講，可能會讓人有個想法，那直接用暴力法不就好了？
暴力法的時間複雜度會是O(n^2)，mehtod的refine就是使用暴力法，我認為這部分是絕對跑不掉的，而這個程式是對於不須使用暴力法的小組用O(n)的算法來計算，來避免暴力法的使用。
我這裡其實沒有做太多的優化，getMaxNumber這個method我想沒甚麼優化的空間，但refine的部分其實還挺有優化的空間

這裡有兩個方向：
1.如果確認有正數存在
在i的迴圈中，可以只對第一個正數或負數之後的第一個正數跑j的迴圈
2.把相鄰的正數直接相乘起來，組成新的小陣列再算O(n^2)的算法
因為這樣「可能」可以把n的數量減少，因而加快速度，但是否真的能加快速度就要看資料的情況了

 

但是以面試來說，我覺得能寫到我寫的code那樣就算很不錯了。如果是我面試遇到的話，我想我因為無法想太多和輕易調整寫過的code，所以是做不到的，大概只會用暴力法的作法解。
就我個人的看法來說，我覺得如果只要口頭回答演算方法，我想這會是個好問題，但如果要寫程式，甚至在紙上寫，那就不是個好題目了(因為code可能會寫太多)