Find the largest possible difference in an array with the smaller integer occurring earlier

user_612673 0
Viewed 16895

This is an interview question:

Find the largest possible difference in an array of integers, such that the smaller integer occurs earlier in the array.

Constraint: Numbers are not unique. The range is Integer range of java. (or any other language)

Example:

input 1: {1, 100, 2, 105, -10, 30, 100}

The largest difference is between -10 and 100 -> 110 (here -10 is at the 5th index and 100 is at 7th index)

input 2: {1, 100, 2, 105, -10, 30, 80}

The largest difference is between 1 and 105 -> 104 (here 1 is at the 1st index and 105 is at 4th index)

Possible Solution:

One approach is check for all possible differences and keep a track of the biggest difference found till now O(n^2) complexity.

can this be done in better than O(n^2) time?

algorithm java
11 Answers
public static void findlargestDifference(int arr[]){

    int max_diff=0;     
    int min_value=Integer.MIN_VALUE;        
    for(int i=0;i<arr.length;i++){

        if(min_value<arr[i]){               
            min_value=arr[i];               
        }           
        int diff=min_value-arr[i];

        if(max_diff<diff){
            max_diff=diff;
        }                   
    }       
    System.out.println("Max Difference is  "+ max_diff);    
}
user_68261970
Related