CODEWITHSUNDEEP
algorithm
Gaaaaaaaa
Gaaaaaaaa

Reputation: 167

find all the local maximum for an array that is either increase or decrease by 1

How to find an algorithm that runs in O(k log n) times, Where k is the number of local maximum and n is the size of the array for example:

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

Upvotes: 1

Views: 87

Answers (1)

Codor
Codor

Reputation: 17605

As a rough idea, you could use the number of maxima (which apparently is known before) as an additional parameter. Check the middle value of the array if it is a local maximum (or the value left or right next to the middle if the number of elements is even). If it is not a local maximum, search the local maxima in the left or right subarray. The formulation in C#-like pseudocode is as follows; if the position of the maxima is needed, some index calculations have to be done additionally.

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);
      }
   }
}

Upvotes: 1

Related Questions