Maximum difference between two elements such that larger element

ghz 10months ago ⋅ 94 views

To find the maximum difference between two elements in an array such that the larger element appears after the smaller number, you can iterate through the array while keeping track of the minimum element encountered so far and the maximum difference found. Here's a Java implementation:

public class MaximumDifference {
    public static int maxDifference(int[] nums) {
        if (nums == null || nums.length < 2)
            return -1; // If array has less than 2 elements, return -1

        int minElement = nums[0];
        int maxDifference = nums[1] - nums[0];

        for (int i = 1; i < nums.length; i++) {
            int currentDifference = nums[i] - minElement;
            maxDifference = Math.max(maxDifference, currentDifference);
            minElement = Math.min(minElement, nums[i]);
        }

        return maxDifference > 0 ? maxDifference : -1; // If maxDifference is positive, return it, else return -1
    }

    public static void main(String[] args) {
        int[] nums = {7, 9, 5, 6, 3, 2};
        System.out.println("Maximum difference: " + maxDifference(nums)); // Output: Maximum difference: 2
    }
}

In this implementation:

  • maxDifference(int[] nums) is the main method that calculates the maximum difference satisfying the condition.
  • We initialize minElement to the first element of the array and maxDifference to the difference between the second and first elements.
  • We iterate through the array starting from the second element. For each element, we calculate the difference between the current element and minElement. If this difference is greater than maxDifference, we update maxDifference. We also update minElement if the current element is smaller than it.
  • Finally, we return maxDifference if it's positive, otherwise, we return -1, indicating that no such pair of elements exists in the array.

You can test this implementation with different arrays to verify its correctness.

#algorithm