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));

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.

1 comment:

  1. An 8-1 payout additionally be} tempting, but with 소울카지노 a 14.36% vigorish, it’s a really bad guess. If the Banker hand totals 7, 8 or 9, the Banker doesn't take one other card. Pro poker participant Maria Ho gives you directions in all the basics to play 3-Card Poker at WinStar World Casino and Resort.