アレイのローカル最大値を1つ増やすか1減らすかを調べる

Question

O(k log n)倍で実行されるアルゴリズムを見つける方法kはローカル最大の数であり、nはアレイのサイズです 例：

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

Answer 1

大まかな考え方として、追加パラメータとしてmaximaの数を使用することができます。ローカル最大値（または要素の数が偶数の場合は中央の左または右の値）の場合は、配列の中間値をチェックします。極大値でない場合は、左または右の部分配列の極大値を検索します。 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); 
     } 
    } 
}