查找數組的所有局部最大值，可以增加或減少1

Question

如何查找在O(k log n)次運行的算法，其中k是局部最大值的數目，n是陣列的大小 例如：

[1,2,3,4,5,6,5,6,7,8,7] 

Answer 1

作爲一個粗略的想法，您可以使用最大值（顯然已知之前）的數量作爲附加參數。檢查數組的中間值，如果它是一個局部最大值（或者如果元素的數量是偶數，則在中間的左邊或右邊的值）。如果它不是局部最大值，則搜索左側或右側子陣列中的局部最大值。 C＃樣僞代碼中的公式如下：如果需要最大值的位置，則需要額外進行一些指標計算。

List<int> Input;   // input array 
List<int> Maxima;   // output for the maxima 
int k;      // num of local maxima 

void SearchMaxima(List<int> iList, int NumOfMaxima) 
{ 
    if (0 == iList.Count() || 0 == NumOfMaxima) 
    { 
    // do nothing 
    } 
    else 
    { 
     if (Middle point of iList is local Maximum) 
     { 
      Store middle point of iList to MaximaPositions 
      SearchMaxima(left half of iList w/o middle point, NumOfMaxima - 1); 
      SearchMaxima(right half of iList w/o middle point, NumOfMaxima - 1); 
     } 
     else 
     { 
      SearchMaxima(left half of iList w/o middle point, NumOfMaxima); 
      SearchMaxima(right half of iList w/o middle point, NumOfMaxima); 
     } 
    } 
}