Wednesday, June 14, 2017

Maximum difference between two elements such that larger element appears after the smaller number


Kadane's Algorithm used partially


if we know the maximum sub-array difference ending at position i, what is the maximum sub-array difference ending at position i + 1 ? The answer turns out to be relatively straightforward: either the maximum sub-array difference ending at position i + 1 includes the maximum sub-array difference ending at position i as a prefix, or it doesn't. Thus, we can compute the maximum sub-array sum ending at position i for all positions i by iterating once over the array by tracking the minimum. As we go, we simply keep track of the maximum sum we've ever seen. Thus, the problem can be solved with the following code, expressed here in Java:


public class MaximumDifference {

public static void main(String[] args) {
int arr[] = { 1, 3, 16, 5, 4, 8, 2, 29 };
int curMin, max_diff;
curMin = arr[0];
max_diff = 0;
for (int i : arr) {
curMin = min(curMin, i);
max_diff = max(max_diff, Math.abs(i - curMin));
}
System.out.println(max_diff);
}

private static int max(int i, int j) {
return i > j ? i : j;
}

private static int min(int i, int j) {
return i < j ? i : j;
}
}




Note: This will also work for all negative numbers where the result will be least negative number.

No comments:

Post a Comment