Java Program to find maximum difference between two elements

public class Main {

    public static void main(String[] args) {
        // code
        int[] arr = {5, 10, 7, 6, 8, 9};
        int maxDiff = getMaxDifference(arr);
        System.out.println("Maximum difference: " + maxDiff);
    }

    private static int getMaxDifference(int[] arr) {
        int n = arr.length;
        int maxDiff = arr[1] - arr[0];
        int minElement = arr[0];

        for (int i = 1; i < n; i++) {
            int currentDiff = arr[i] - minElement;
            maxDiff = Math.max(currentDiff, maxDiff);
            minElement = Math.min(arr[i], minElement);
        }

        return maxDiff;
    }
}

In this program, we first declare an array arr with some sample values. Then, we call the getMaxDifference function which takes an array as input and returns the maximum difference between any two elements in the array.

Inside the getMaxDifference function, we first initialize maxDiff to the difference between the second and first elements of the array. We also initialize minElement to the first element of the array.

We then loop through the remaining elements of the array, starting from the second element. For each element, we check if the difference between the current element and minElement is greater than the current value of maxDiff. If it is, we update maxDiff to the new difference. We also update minElement if the current element is less than the current value of minElement.

Finally, we return the value of maxDiff, which is the maximum difference between any two elements in the array.

When we run this program, it should output:

Maximum difference: 5

The time complexity of the getMaxDifference function in the Java program I provided is O(n), where n is the length of the input array.

The reason for this is that the function uses a single loop to iterate through the entire array, which takes O(n) time in the worst case. Within the loop, there are only a constant number of operations being performed, such as comparisons and updates to the maxDiff and minElement variables, which take O(1) time.

Therefore, the overall time complexity of the function is O(n), since the loop dominates the overall running time.

In terms of space complexity, the function uses a constant amount of extra space to store the maxDiff and minElement variables, as well as the loop counter i. Therefore, the space complexity is O(1), which is constant.