title: Monotonic Pair - Codility
body: <p>I was just at Codility, and ran into a task for which I can't find a solution in targeted O(n) efficiency; my solution runs for O(n2). I would be very pleased if someone could just give me a hint on how to get it run faster. Here is the task.</p>
  
  <p>A non-empty zero-indexed array A consisting of N integers is given.</p>
  
  <p>A monotonic_pair is a pair of integers (P, Q), such that 0 ≤ P ≤ Q &lt; N and A[P] ≤ A[Q].</p>
  
  <p>The goal is to find the monotonic_pair whose indices are the furthest apart. More precisely, we should maximize the value Q − P. It is sufficient to find only the distance.</p>
  
  <p>For example, consider array A such that:</p>
  
  <pre><code>A[0] = 5
  A[1] = 3
  A[2] = 6
  A[3] = 3
  A[4] = 4
  A[5] = 2
  </code></pre>
  
  <p>There are eleven monotonic_pairs: (0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5). The biggest distance is 3, in the pair (1, 4).</p>
  
  <p>Write a function:</p>
  
  <p>class Solution { public int solution(int[] A); }</p>
  
  <p>that, given a non-empty zero-indexed array A of N integers, returns the biggest distance within any of the monotonic_pairs.</p>
  
  <p>For example, given:</p>
  
  <pre><code>A[0] = 5
  A[1] = 3
  A[2] = 6
  A[3] = 3
  A[4] = 4
  A[5] = 2
  </code></pre>
  
  <p>the function should return 3, as explained above.</p>
  
  <p>Assume that:</p>
  
  <p>N is an integer within the range [1..300,000];
  each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
  Complexity:</p>
  
  <p>expected worst-case time complexity is O(N);
  expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
  Elements of input arrays can be modified.</p>
  
  <p>And my 1st idea solution (runs in O(n2)):</p>
  
  <pre><code>    public static int solution(int[] A) {
      int max = 0;
      for(int i=0; i&lt;A.length-1; i++) {
          for(int j=i+1; j&lt;A.length; j++) {
              if(A[j] &gt;= A[i] &amp;&amp;
                      (j - i) &gt;= max) {
                  max = j - i;
              }
          }
      }
      return max;
  }
  </code></pre>