Largest Difference in an Array

Question

You have an array of integers:
int[] A = { 10, 3, 6, 8, 9, 4, 3 };
My goal is to find the largest difference between A[Q] and A[P] such that Q > P.

If P = 1 and Q = 4

diff = A[Q] – A[P]
diff = 9 – 3
diff = 6
Since 6 is the largest number between all the difference, that is the answer.

Answer 1

algorithm:
1) consider an array 10,3,6,8,9,4,3. start from the 2nd ele. do 3-10=-7 save it in deatination array b[0]
2) consider 3rd ele 6. do 6-3=3, 6-10=-4 and 3>-4 so save 3 in b[1]
3}similarly consider 4th ele 8. do 8-6=2, 8-3=5, 8-10=-2 and 5>2>-2. therefore save 5 in b[2]
4)similary do for all ele. b[] will be -7 3 5 6 1 0. b[] size is one less than the given arr a[] because u ll start from 2nd ele in step 1).
5) the largest ele in the b[] is 6. therefore it ll be the highest difference between two ele in the array.

#include<stdio.h>

int main()
{
    int a[]={10,3,6,8,9,4,3};
    int na=7; // given array size
    int b[6]; //  destination array should be 1 less than the given array a[]
    int nb=6; // destination array size b[]
    int i,j,temp=-999,temp2=-999; //consider temp as the very smallest integer possible
    int max;

    for(i=1;i<na;i++)
    {
        for(j=i-1;j>=0;j--)
        {
            max=a[i]-a[j];
            temp2=max; // save max

            if(temp>max) //comparing previous iteration with the current iteration n keep the highest val in **max**
                max=temp;
            temp=temp2; //saved max in temp. temp ll always have the previous iteration value 
        }
        b[i-1]=max;

    }

    max=b[0]; // find the biggest ele in the dest arr b[] to find the highest diff
    for (i=0;i<nb-1;i++)
    {
        if(b[i+1]>max)
            max=b[i+1];
    }
    printf("max=%d\t",max);
    return 0;
}

Comments

Please add some lines as part of algo so that it can help people to understand the code. Just use the edit button...:)