Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Maximum Difference in an Array

Sharing is caring!

Problem Statement
You are given an array of integers and must compute the maximum difference between any item and any lower indexed smaller item for all the possible pairs, i.e., for a given array 'a', find the maximum value of a[j] - a[i] for all i, j where 0 ≤ i < j < n and a[i] < a[j]. If no item has a smaller item with a lower index, then return -1.

For example, given an array [1, 2, 6, 4], you would first compare 2 to the elements to its left. 1 is smaller, so calculate the difference 2 – 1 = 1. 6 is bigger than 2 and 1, so calculate the differences 4 and 5. 4 is only bigger than 2 and 1, and the differences are 2 and 3. The largest difference was 6 – 1 = 5.

Function Description
Complete the function maxDifference in the editor below. The function must return an integer representing the maximum difference in a.

maxDifference has the following parameter(s):
* a[a[0],a[1],…a[n-1]]: an array of integers

Constraints
1 ≤ n ≤ 2 × 105
−106 ≤ a[i] ≤ 106 ∀ i ∈ [0, n − 1]

Sample Input 0

7
2
3
10
2
4
8
1

Sample Output

8

Explanation
n = 7, a = [2, 3, 10, 2, 4, 8, 1]

Differences are calculated as:

3 – [2] = [1]
10 – [3, 2] = [7, 8]
4 – [2, 3, 2] = [2, 1, 2]
8 – [4, 2, 3, 2] = [4, 6, 5, 6]
The maximum is found at 10 – 2 = 8.

Solution

class MaxDifferenceInArray2 {
    public static int maxDifference(List<Integer> a) {
        int n = a.size();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = a.get(i);
        }

        int[] min = new int[n]; // min[i] min up to index i
        min[0] = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] < min[i - 1]) {
                min[i] = arr[i];
            } else {
                min[i] = min[i - 1];
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            if (arr[i] > min[i - 1]) {
                max = Math.max(max, (a.get(i) - min[i - 1]));
            }
        }

        if (max == Integer.MIN_VALUE) {
            return -1;
        } else {
            return max;
        }
    }

    public static void main(String[] args) throws FileNotFoundException {
        System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in.txt"));
        //Scanner outputScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "out.txt"));

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        List<Integer> a = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(scanner.next());
            a.add(x);
        }

        System.out.println(a);

        System.out.println(maxDifference(a));
    }
}