Fidelity Question3: You are given an array of random positive and negative numbers.

You need to find the largest difference among all differences between two numbers in such a way that: 0<=i<n ; i<=j<n; ar[j]>ar[i] and the difference is ar[j]-ar[i].

For example: in array {2,3,1,5,4,7,9}

For 3 :{1} , max of set :1

For 1 :{} , empty as 1 is not bigger than any element in left

For 5 :{3,2,4} , max of set=4

For 4 :{2,1,3} , max of set=3

For 7 :{5,4,6,2,3} , max of set=6

For 9 :{7,6,8,4,5,2}, max of set=8

So the answer is the max of all above results{1,4,3,6,8} i.e 8.

If if you cannot get the required result return -1;

PS: (The question description is made easier than the original one)

Implementation:

Output:

7

2

3

4

1

5

7

9

The resultant maximum difference is 8