Programmer's Blog

Programmer's reference

[C++] find maximum in each of subsequence

problem: Find max in each of the 3 numbers in the sequence

2 3 1 5 6 3 6

ans: 3 5 6 6 6

void printKMax(int arr[], int n, int k){
 deque<int> d;
 int max = 0;
 int maxpos = 0;
 for (int i = 0 ; i < n ; i++)
 {
     d.push_back(arr[i]);
     if (d.size() > k) d.pop_front(); //if size > subseq, drop

     if (max < d.back())  //compare first number in deque
     {
         max = d.back();
         maxpos = k - 1;
     }
     else
         maxpos--;        //the pos in maximum in subseq shifts
 
     if (maxpos <= 0)  //if max num is out of deque
     {                 //check all numbers in the subseq
         max = 0;
         for (int j = 0 ; j < d.size() ; j++)
         {
             if (max < d.back())
             {
                 max = d.back();
                 maxpos = j;
             }
             d.push_back(d.front());
             d.pop_front();
     } 
 }
 
 if (d.size() < k)
 continue;

 cout << max << " ";
}
 
 
 cout << "\n";
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: