# Maximum Difference in an Array

**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**

1 2 3 4 5 6 7 8 9 |
7 2 3 10 2 4 8 1 |

**Sample Output**

1 2 |
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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
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)); } } |