Find the max. difference between two array elements a[j] and a[i] such that j > i

Question

The source of the problem is here.

Given an array of integer elements, return the maximum difference of any pair of numbers such that the larger number of the pair occurs at a higher index than the smaller.

Here is my implementation in Java.

package algo.mindiff;
public class Main {
 // http://www.careercup.com/question?id=5185822661804032
 public static void main(String[] args) {
 System.out.println(minDiff(new int[] { 10, 1, 12, 3, 4, 28, 1 }));
 }
 private static int minDiff(int[] array) {
 int diff = 0;
 int result = 0;
 for (int i = 0; i < array.length;) {
 int maxIndex = maxIndex(array, i);
 int minIndex = minIndex(array, i, maxIndex);
 diff = array[maxIndex] - array[minIndex];
 if (result < diff)
 result = diff;
 i = maxIndex + 1;
 }
 return result;
 }
 private static int minIndex(int[] array, int start, int end) {
 int min = start;
 for (int i = start + 1; i < end; i++) {
 if (array[i] < array[min]) {
 min = i;
 }
 }
 return min;
 }
 private static int maxIndex(int[] array, int start) {
 int max = start;
 for (int i = start + 1; i < array.length; i++) {
 if (array[i] >= array[max]) {
 max = i;
 }
 }
 return max;
 }
}

And here is a brief summary of my algorithm:

1. I find the maximum element in the given array. Its index is maxIndex.
2. Then I find the minimum element within the range [0, maxIndex). Its index is minIndex.
3. If the difference result I calculated last time is less than the difference diff between array[maxIndex] and array[minIndex], I'll just assign the new value to result.
4. I do steps 1 - 3 for the other elements of the array starting with maxIndex + 1.

If my algorithm doesn't work on any input data you might have in mind, please let me know.

• Comintern: Obviously not a full answer, but you should only have to traverse the array once.
• Maksim Dmitriev: @Comintern, I traverse the array once
• Comintern: It only goes through the array once completely, but it scans it twice and checks the bounds 4 times with your input array.

Answer 1

The algorithm you're using does a bunch of superfluous work. It would be much more efficient to concentrate on tracking the maximum difference that conforms to the specification than where you are in the array.

Setting the maxIndex the first time through your main loop isn't really setting any meaningful limit for you, because you also need to check to see if there are any other number combinations that have a higher difference than just the array maximum. In fact, you don't need to know what the highest value is at all or it's position in the array. The highest difference already assumes both of these, because when you set the greatest difference it is calculated based on the lowest value up to the current point in the array.

The idea of limiting the minimum check to the position of the previous high is well intentioned, but why not just run through the array once and keep track of everything at the same time?

The pseudo-code is much simpler:

• Set the first value in the array to your low value.
• Loop through the array.
• If the current element minus the low value is higher than the maximum difference found, update the maximum difference.
• If the current element is lower than the previous low, update the previous low value.
• Return the maximum difference when you hit the end of the array.

• Akash: Sanity check, but is it as simple as ideone.com/FPLWIN ? (just a direct implementation of the algo you wrote)
• Comintern: @Akash - Simpler. ideone.com/hN0kUv
• Snehasish: @Comintern: Just to confirm, can it be done if we traverse the array from the right, keeping track of the max element found so far and the max difference (max element found - current element) found so far?