Your algo is good but i don get the part where A[i] (current element) is less than the first element? Do we enqueue it? And if yes, when the front element is popped out , how is the next max found in front of the queue? If you could give an example with the growing queue.
On Friday, 2 September 2011 15:43:41 UTC+5:30, WgpShashank wrote: > > Hi Anup , here is naive approach > > There is a sliding window of size w which is moving from the very left of > the array to the very right. You can only see the w numbers in the window. > Each time the sliding window moves rightwards by one position. > > Following is an example: > The array is [1 3 -1 -3 5 3 6 7], and w is 3. > > Window position Max > --------------- ----- > [1 3 -1] -3 5 3 6 7 3 > 1 [3 -1 -3] 5 3 6 7 3 > 1 3 [-1 -3 5] 3 6 7 5 > 1 3 -1 [-3 5 3] 6 7 5 > 1 3 -1 -3 [5 3 6] 7 6 > 1 3 -1 -3 5 [3 6 7] 7 > > The obvious solution with run time complexity of O(nw) is which is not > efficient enough. Every time the window is moved, we have to search for the > maximum from w elements in the window. where w is size of window & n is > size of array > > 1st Method(Naive Approach) > > Data Structure Used : Array > Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in > window) > B.for all j=i to i+w (keep incrementing windows size form left to right) > C find maximum inn each window & print it or put in array (Auxiliary) > > For more efficient approaches you can have a look here > > http://shashank7s.blogspot.com/2011/06/given-array-and-integer-k-find-maximum.html > > correct me if anything wrong or other approaches you can thing of ? > > Thanks > Shashank Mani > Computer Science > Birla Institute of Technology Mesra > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/giQA3tSNZtAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
