Re: [討論] 面試遇到的考題

[CLFJ ()]

※ 引述《sleeper0121 (sleeper)》之銘言：
: 今天去面試，裡面有題題目是這樣:
: 寫個函式，傳個整數陣列進去，陣列裡面的整數可以是正數、負數或 0
: 請回傳一個陣列裡面相鄰互乘的最大整數值
: 例如: [2 , -7 , 0  , 2 , 3 , 8 , -6 , 5]
: 就是 2 * 3 * 8 = 48
: 再一個例子: [-2 , 0 , 3 , 5 , -7]
: 就是 3 * 5 = 15
: 請問這題思考邏輯大概是怎樣呢?
: 當下沒解出來，害我回家後還一直再想    XD


 剛想一下寫的，希望大家幫忙指教一下有沒有邏輯上的瑕疵

function int ArrayMax(int[] arr)
{
      // 宣告一個最後要回傳的結果
      int MaxValue = 0;

      // 如果array長度只有1，就自己傳回去
      if(arr.length == 1)
            return arr[0];

      // 在下一個loop中紀錄參數的arr中有沒有出現任何一個0
      bool hasZero = false;

      // 開始scan arr中有沒有0，遇到0遞迴送進前一段沒有0的array. 
      //因為0ㄧ乘就變0
      int startIndex = 0;
      for(int i=0; i<arr.length; i++)
      {
            if(arr[i] == 0)
            {
                  // 整個array有至少一個0，不用整個乘在一起
                  hasZero  = true;

                  if(i > startIndex)
                  {
                        int temp = ArrayMax(subarray[startIndex  ... (i-1)]);
                        if(MaxValue  < temp)
                              MaxValue   = temp;
                        startIndex =  i + 1;
                  }
            }
      }

      // 只要有任何一個0被找到，就表示分段都算完了，傳回MaxValue
      if(hasZero)
            return MaxValue ;


      // 否則，整個array都沒有0. 再scanㄧ次找出幾個負號
      int NegativeCount = 0;

      // FirstNegativeIndex 是第一個負號出現的位置
      // LastNegativeIndex 是最後一個負號出現的位置
      int FirstNegativeIndex = -1;
      int LastNegativeIndex = -1;

      for(int i=0; i<arr.length; i++)
      {
            if(arr[i] <0)   // 發現負數
            {
                  NegativeCount++;

                  if(FirstNegativeIndex == -1)
                  {
                        FirstNegativeIndex  = i;
                  }

                  LastNegativeIndex = i;
            }
      }

      // 若發現偶數個負號又沒有0，整個相乘ㄧ定是正值，直接array每一個直接
      // 相乘後傳回結果
      if(NegativeCount % 2 ==0)
      {
            return arr[0]*arr[1]*...*arr[length-1];
      }
      else
      {
            // 奇數個負號則找出第一個和最後一個，把這兩個負號當切割點處理.
            // 分別計算這兩個負號切割出的四個array能找出的MAX是多少
            return MAX(
                  ArrayMax(arr[LastNegativeIndex+1 ... length-1],
                  ArrayMax(arr[0 ... LastNegativeIndex-1],
                  ArrayMax(arr[FirstNegativeIndex+1 ... length-1],
                  ArrayMax(arr[0 ... FirstNegativeIndex-1]);
      }
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.43.215
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1404404289.A.D2D.html
※ 編輯: CLFJ (122.116.43.215), 07/04/2014 09:34:22
推 BruceX:比較喜歡你的做法