Maximizing Difference Between Two Ordered Elements

The concept of Maximizing Difference Between Two Ordered Elements is about finding two elements in a sequence, ordered by their appearance, such that the difference between the second and the first element is as large as possible. The challenge is to identify these two elements in a way that ensures the first element precedes the second one in the sequence.

Solution

Below are code implementations for this concept in Java, C++, and Python:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class MaxDifference {
    public static int maxDifference(int[] arr) {
        int minElementSoFar = arr[0];
        int maxDifference = 0;

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

        return maxDifference;
    }

    public static void main(String[] args) {
        int[] values = {7, 1, 5, 3, 6, 4};
        System.out.println(maxDifference(values)); // Output: 5
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
#include <algorithm>

int maxDifference(std::vector<int> arr) {
    int minElementSoFar = arr[0];
    int maxDifference = 0;

    for (int i = 1; i < arr.size(); i++) {
        maxDifference = std::max(maxDifference, arr[i] - minElementSoFar);
        minElementSoFar = std::min(minElementSoFar, arr[i]);
    }

    return maxDifference;
}

int main() {
    std::vector<int> values = {7, 1, 5, 3, 6, 4};
    std::cout << maxDifference(values); // Output: 5
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def max_difference(arr):
    min_element_so_far = arr[0]
    max_difference = 0

    for value in arr[1:]:
        max_difference = max(max_difference, value - min_element_so_far)
        min_element_so_far = min(min_element_so_far, value)

    return max_difference

values = [7, 1, 5, 3, 6, 4]
print(max_difference(values))  # Output: 5

These code samples implement a simple approach that iterates through the given sequence, keeping track of the smallest element so far. At each step, they calculate the difference between the current element and the smallest one, updating the maximum difference if the calculated difference is greater. The result is the maximum difference between any two ordered elements in the sequence.