..MindWrite..

Posts Tagged ‘j>i’

Find the index i and j of an array where j>i and a[j] – a[i] is maximum

Posted by guptaradhesh on March 27, 2013

 

Given an unsorted array, find the index i and j such that, j>i and (a[j] – a[i]) is maximum?

A linear time solution which I find pretty elegant:

       private void MaxDiff(int[] a)
       {
           int min = a[0]; // assume first element as minimum
           int maxdiff = 0;
           int posi = -1, posj = -1, minpos = 0;

           for (int i = 1; i < a.Length; i++)
           {
               if (a[i] < min)
               {
                   min = a[i];
                   minpos = i;
               }
               else
               {
                   int diff = a[i] - min;
                   if (diff > maxdiff)
                   {
                       maxdiff = diff;
                       posi = minpos;
                       posj = i;
                   }
               }
           }
           System.out.format("i=%d, j=%d",posi,posj);
       }
Advertisements

Posted in puzzles/ algorithms | Tagged: , , , , | Leave a Comment »