C ++ algorithm for finding the "maximum difference" in an array

Question

I ask for your ideas regarding this issue:

I have one array A containing N double elements (or alternatively an integer). I would like to find an algorithm with complexity less than O (N ² ) to find:

  max A[i] - A[j] 

For 1 <j <= i <n. Note that there is no abs() . I thought:

• dynamic programming
• dichotomous method, divide and conquer
• some processing after sorting with index tracking

Do you have any comments or ideas? Could you point out some good ref in order to train or make progress to solve such questions of the algorithm?

Answer 1

Do three sweeps through the array. First, from j=2 up, filling the auxiliary array a minimum element so far. Then drill down from top i=n-1 , filling (also top to bottom) another auxiliary array, b , with the maximum element so far (top). Now sweep both auxiliary arrays, looking for the maximum difference b[i]-a[i] .

That will be the answer. O(n) as a whole. You can say that it is a dynamic programming algorithm.

edit:. As an optimization, you can eliminate the third sweep and the second array and find the answer in the second sweep, supporting two loop variables, max-so-far-from-the -top and max-difference.

As for the “pointers” on how to solve such problems in general, you usually try to use some common methods, as you wrote, - share and win, memoization / dynamic programming, etc. First of all, carefully study your problems and concepts. Here it is maximum / minimum. Separate these concepts and see how these parts come together in the context of the problem, possibly changing the order in which they are calculated. Another is looking for hidden order / symmetry in your problem.

In particular, fixing an arbitrary interior point k in the list, this problem reduces to finding the difference between the minimum element among all j such that 1<j<=k and the maximum element among i s: k<=i<n . You see here the separation and conquest, as well as the differentiation of the concepts max / min (i.e., their progressive calculation) and the interaction between the parts. A hidden order is displayed ( k goes through the array), and memoization helps preserve intermediate results for max / min values.

Fixing an arbitrary point k can be considered as solving a smaller sub-problem first ("for a given k ...") and finding out if there is something special in it, and it can be canceled - generalized - abstracted.

First, there is a method that allows you to first formulate and solve a big problem, so that the original problem is part of this larger one. Here we are thinking of finding all the differences for each k, and then finding the maximum of them.

The double use of intermediate results (used both in comparison for a particular point k and in calculating the next intermediate result in each direction) usually means significant savings. So,

• divide and rule
• memoization / dynamic programing
• hidden order / symmetry
• separation of concepts - type of use of components
• dual use - locate dual use parts and save them.
• solution to a big problem
• attempt to arbitrary subtask and abstract on it

Answer 2

This should be possible in one iteration. max(a[i] - a[j]) for 1 <j <= i should be the same as max[i=2..n](a[i] - min[j=2..i](a[j])) , right? Therefore, you will need to track the smallest a[j] when repeating the array, looking for the largest a[i] - min(a[j]) . This way you will only have one iteration, and j will be less than or equal to i.

Answer 3

You just need to go through the array, find max and min, then get the difference, so the worst case is linear time. If the array is sorted, can you find diff in constant time or am I missing something?

Answer 4

Java implementation runs in linear time

 public class MaxDiference { public static void main(String[] args) { System.out.println(betweenTwoElements(2, 3, 10, 6, 4, 8, 1)); } private static int betweenTwoElements(int... nums) { int maxDifference = nums[1] - nums[0]; int minElement = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] - minElement > maxDifference) { maxDifference = nums[i] - minElement; } if (nums[i] < minElement) { minElement = nums[i]; } } return maxDifference; } }