title: Minimum difference between sum of two numbers in an array
body: <p>I am trying to solve this <a href="https://www.hackerearth.com/problem/algorithm/project-team/description/" rel="nofollow noreferrer">problem</a>:</p>
  <blockquote>
  <p>A Professor of Physics gave projects to the students of his class. The students have to form a team of two for doing the project. The professor left the students to decide the teams. The number of students in a class will be even.</p>
  <p>Each student has a knowledge level. It tells how much knowledge each student has. The knowledge level of a team is the sum of the knowledge levels of both the students.</p>
  <p>The students decide to form groups such that the difference between the team with highest knowledge and the one with lowest knowledge is minimum.</p>
  <p>Input</p>
  <p>First line of the input will contain number of test cases t; In the next t lines the first number is n the number of students in the class followed by n integers denoting the knowledge levels of the n students</p>
  <p>Output</p>
  <p>Your output should be a single line containing the lowest possible difference between the team with highest knowledge and the one with lowest knowledge.</p>
  </blockquote>
  <p>The solution boils down to calculate minimum difference between sum of two numbers in an unsorted array. So far I have tried:</p>
  <ol>
  <li>Sort the array.</li>
  <li>Add elements at positions i and n-i-1 and take its absolute difference with sum of elements at position i+1 and n-i.</li>
  <li>Store the differences in priority queue.</li>
  <li>Pop the top of priority queue to get the answer.</li>
  </ol>
  <p>And, here is the code I have tried:</p>
  <pre><code>#include &lt;bits/stdc++.h&gt;
  using namespace std;
  
  int main()
  {
      ios_base::sync_with_stdio(false);
  
      int T=0,num=0;
      cin &gt;&gt; T;
      
      while(T--){
          cin &gt;&gt; num;
          int *a = new int[num];
          for(int i = 0; i &lt; num; i++){
              cin &gt;&gt; a[i];
          }
          sort(a,a+num);
          priority_queue&lt;int&gt; pq;
          for(int i = 0; i &lt; num-2; i++){
              int j = i+1;
              pq.push(abs(a[i]+a[num-1-i]-a[j]-a[num-j-1]));
          }
          cout &lt;&lt; pq.top()&lt;&lt; endl;
      }
      return 0;
  }
  </code></pre>
  <p>This solution exceeds the time limit and my intuition is it may fail for some cases.
  The description and tags hint of a dynamic programming solution but somehow I am not able to deduce the optimal substructure. Can anyone help?</p>