title: Maximum and Minimum Value for Triplet
body: <p>I have a Java computational problem in which I am given an array of integers:</p>
  
  <p>For example:</p>
  
  <p>3 -2 -10 0 1</p>
  
  <p>and I am supposed to compute what is the minimal integer and maximum triplet that
  can be formed from these integers. (In this case, min=-30,max=60)</p>
  
  <p>I initially thought that the maximum would always be positive and minimum would always be
  negative.</p>
  
  <p>Hence,</p>
  
  <p>My initial algorithm was:</p>
  
  <ol>
  <li>Scan the array and take out the 3 largest elements inside, store into an array.</li>
  <li>At the same time, take out the 3 smallest elements inside, store into another array.</li>
  </ol>
  
  <p>By inequalities, we can deduce the following:</p>
  
  <p>+ve = (-)(-)(+) or (+)(+)(+)</p>
  
  <p>-ve = (+)(+)(-) or (-)(-)(-)</p>
  
  <p>Hence, I used the elements from the two arrays that I computed to try to obtain the maximal and minimal triplet. (i.e. In order to obtain the maximal triplet, I compared the triplet formed by the largest 3 with the triplet formed by the smallest 2 and the largest integer)</p>
  
  <p>However, I realized that if all the given integers were negative, my algorithm would be defeated because of the fact that the maximal would be negative. (Vice-versa for minimal)</p>
  
  <p>I know that I can simply add more checks to solve this problem or simply just use the brute force O(N^3) solution. But there must be a better way to solve this problem.</p>
  
  <p>This problem must be solved by recursion and only in O(N) time.</p>
  
  <p>I am in a fix. Could someone please guide me?</p>
  
  <p>Thanks.</p>