title: Finding maximum of minimum for every window size in a given array
body: <p>An integer array A[] of size N is given.The task is to find the maximum of the minimum of every window size in the array.
  Note: Window size varies from 1 to n.</p>
  
  <p>E.g:arr[] = {10, 20, 30, 50, 10, 70, 30}</p>
  
  <p>Output:     70, 30, 20, 10, 10, 10, 10</p>
  
  <p>I understood how the output came But I am really having trouble in understanding the algorithm.I understood the naive approach but the solution that involves O(n) is quiet tricky to understand.The code for O(n) is attached below:</p>
  
  <pre><code>import java.util.Stack; 
  class Test { 
  static int arr[] = {10, 20, 30, 50, 10, 70, 30}; 
  static void printMaxOfMin(int n) 
  { 
      // Used to find previous and next smaller 
      Stack&lt;Integer&gt; s = new Stack&lt;&gt;(); 
  
      // Arrays to store previous and next smaller 
      int left[] = new int[n+1]; 
      int right[] = new int[n+1]; 
  
      // Initialize elements of left[] and right[] 
      for (int i=0; i&lt;n; i++) 
      { 
          left[i] = -1; 
          right[i] = n; 
      } 
  
      // Fill elements of left[] using logic discussed on 
      // https://www.geeksforgeeks.org/next-greater-element/ 
      for (int i=0; i&lt;n; i++) 
      { 
          while (!s.empty() &amp;&amp; arr[s.peek()] &gt;= arr[i]) 
              s.pop(); 
  
          if (!s.empty()) 
              left[i] = s.peek(); 
  
          s.push(i); 
      } 
  
      // Empty the stack as stack is going to be used for right[] 
      while (!s.empty()) 
          s.pop(); 
  
      // Fill elements of right[] using same logic 
      for (int i = n-1 ; i&gt;=0 ; i-- ) 
      { 
          while (!s.empty() &amp;&amp; arr[s.peek()] &gt;= arr[i]) 
              s.pop(); 
  
          if(!s.empty()) 
              right[i] = s.peek(); 
  
          s.push(i); 
      } 
  
      // Create and initialize answer array 
      int ans[] = new int[n+1]; 
      for (int i=0; i&lt;=n; i++) 
          ans[i] = 0; 
  
      // Fill answer array by comparing minimums of all 
      // lengths computed using left[] and right[] 
      for (int i=0; i&lt;n; i++) 
      { 
          // length of the interval 
          int len = right[i] - left[i] - 1; 
  
          // arr[i] is a possible answer for this length 
          // 'len' interval, check if arr[i] is more than 
          // max for 'len' 
          ans[len] = Math.max(ans[len], arr[i]); 
      } 
  
      // Some entries in ans[] may not be filled yet. Fill 
      // them by taking values from right side of ans[] 
      for (int i=n-1; i&gt;=1; i--) 
          ans[i] = Math.max(ans[i], ans[i+1]); 
  
      // Print the result 
      for (int i=1; i&lt;=n; i++) 
          System.out.print(ans[i] + " "); 
  } 
  
  // Driver method 
  public static void main(String[] args) 
  { 
      printMaxOfMin(arr.length); 
  } }
  </code></pre>
  
  <p>The above attached code can be found on <a href="https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/find-the-maximum-of-minimums-for-every-window-size-in-a-given-array/</a> </p>