title: Finding a sub-array where every pair has sum greater than a given K
body: <p>I have been given an array A of integers. Now I have to found out a sub-array(a sub-sequence of original array) where sum of every pair is greater than or equal to a pre-defined K.</p>
  
  <p>What I thought :-</p>
  
  <ul>
  <li>Will sort the array in O(nlgn) or O(n) depending upon range of values in array.</li>
  <li>Find out i in sorted array such that <code>sorted[i] + sorted[i+1]&gt;=k</code></li>
  <li>Set max to <code>sorted[i]</code></li>
  <li>Traverse the original array to delete all value smaller than max, which is the required sub-sequence</li>
  </ul>
  
  <p>Repeat the above for all the elements of the array.</p>
  
  <p>Running Time :- <code>O(nlgn)</code></p>
  
  <p>Is the solution optimal ? Can we further improve it ?</p>
  
  <p>Example :-</p>
  
  <pre><code>-10 -100 5 2 4 7 10 23 81 5 25
  </code></pre>
  
  <p>Sorted Array</p>
  
  <pre><code>-100 -10 2 4 5 5 7 10 23 25 81
  </code></pre>
  
  <p>Let <code>K = 20</code></p>
  
  <p>Sub Array : - </p>
  
  <p>10 23 25 81</p>
  
  <p>Had the question been to find out longest sub-array, algorithm suggested by alestanis in the answers would work fine :)</p>