title: How can we find second maximum from array efficiently?
body: <p>Is it possible to find the second maximum number from an array of integers by traversing the array only once?</p>
  
  <p>As an example, I have a array of five integers from which I want to find second maximum number.  Here is an attempt I gave in the interview:</p>
  
  <pre><code>#define MIN -1
  int main()
  {
      int max=MIN,second_max=MIN;
      int arr[6]={0,1,2,3,4,5};
      for(int i=0;i&lt;5;i++){
          cout&lt;&lt;"::"&lt;&lt;arr[i];
      }
      for(int i=0;i&lt;5;i++){
          if(arr[i]&gt;max){
              second_max=max;
              max=arr[i];          
          }
      }
      cout&lt;&lt;endl&lt;&lt;"Second Max:"&lt;&lt;second_max;
      int i;
      cin&gt;&gt;i;
      return 0;
  }
  </code></pre>
  
  <p>The interviewer, however, came up with the test case <code>int arr[6]={5,4,3,2,1,0};</code>, which prevents it from going to the <code>if</code> condition the second time. 
  I said to the interviewer that the only way would be to parse the array two times (two <code>for</code> loops).  Does anybody have a better solution?</p>