Q. Find the maximum difference between two elements i and j a[i] -a[j] where j>i

Example:

{1,23,56,24,76,89,123,32,47,94}

a[i]=123  and  a[j]=32

answer  is  123 - 32= 91

(see  -122  will  not  be  answer  here  we  dont  have  to  calculate  absolute  one... )

METHOD 1

A  completely  naive  method  in  which  for  every  element  we  calculate  difference  with  the  left  out  elements  and  maintain  the  maximum  difference.  This  method  will  not  be  expected  in  interviews .

for(i=0 to n)

{

for(j=i to n)

result=compute a[i]-a[j]

if(result>maxYet)

maxYet=result;

}

#include<stdio.h>
int main()
{
int result=0;
int arr[10]={1,23,56,24,76,89,123,32,47,94};
int minNumber=arr[9];
int maxResult=0;
for(int k=9;k>=0;k--)
{
for(int k1=9;k1>=k;k1--)
{
int diff=arr[k]-arr[k1];
if(result<diff)
result=diff;
}
}
printf("%d",result);
return 0;
}

Space  Complexity=O(1)

Time   Complexity=O(n^2)

METHOD 2

One  scan  method  for  this   is  to  scan  the  elements  from  right  only  and  calculate 

result= a[i]-min(a[i+1....n])

maximum  of  result  is  our  answer

max=0;

for(j=n  to  0)

{

result= a[j]-min(a[j  to  n])

if(max<result)

result=max;

}

#include<stdio.h>
int main()
{
int arr[10]={1,23,56,24,76,89,123,32,47,94};
int minNumber=arr[9];
int maxResult=0;
for(int k=9;k>=0;k--)
{
if(minNumber>arr[k])
minNumber=arr[k];
int result=arr[k]-minNumber;
if(result>maxResult)
maxResult=result;
}
printf("%d",maxResult);
return 0;
}

Space  Complexity=O(1)

Time  Complexity=O(n)