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/-/m1R83UHfc2UJ. 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.
