Friday, 21 July 2017

Algorithms | Maximum difference between two elements where larger element appears after the smaller number

Given an array of integers, find out the difference between any two elements such that larger element appears after the smaller number in the array.

Examples:
If an array is {80, 2, 6, 3, 100} then returned value should be 98 (Difference between 100 and 2).

package com.algorithms.forum.array;
/**
 * In a given array of numbers, identify maximum difference between
 * 2 numbers such that array[i]<array[j] where i<j.
 * @author algos.debug
 */
public class MaximizeDifference {
    
     private static int getMaximumDiff(int[] array) {

           int length = array.length;
           int maxSoFar = array[length-1];
          
           int maxDiff = Integer.MIN_VALUE;
          
           for (int i = length-2; i >=0 ; i--) {
                maxDiff =  Math.max(maxSoFar-array[i], maxDiff);
                maxSoFar = Math.max(array[i], maxSoFar);
           }
           return maxDiff;
     }
    
     public static void main(String[] args) {
           int[] array = {80, 2, 6, 3, 100};
          
           int diff = getMaximumDiff(array);
          
           System.out.println(diff);
     }
}
Output: 98

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...