CareerCup

More generalized form of the problem where attempting to get the maximum a[m] - a[n] where m - n >= 1 instead of m - n == 1 .

O(n) runtime with O(1) memory:

//returns -1 if no drop from some a[m] to a[n] where m < n could be computed
public static int maxDrop(int[] arr){
    if(arr == null){
        throw new NullPointerException();
    }
    if(arr.length == 0){
        return -1;
    }

    int bestDiff = -1;
    int max = arr[0];
    int currentDiff = -1;
    
    for(int i = 0; i < arr.length; i++){
        int val = arr[i];
        if(val > max){
            max = val;
            currentDiff = -1;
        }
        else{
            int diff = max - val;
            if(diff > currentDiff){
                currentDiff = diff;
                if(currentDiff > bestDiff){
                    bestDiff = currentDiff;
                }
            }
        }
    }
    return bestDiff;
}

The solution can be done using dynamic programming. Take another array max of size n.
Max[i] would be the maximum value from a[n] till a,[I]. After constructing this Mac array, simply take the diff using a[I] and max[I] and the max diff among them would be the answer. Time complexity would be O(n) but spacd complexity would be O(n)

public class MaxDifferenceSvc
{
	public static int findMaxDifference(int[] a) throws NullPointerException
	{
		if(a==null)
		{
			throw new NullPointerException();
		}
		
		int maxDiff=0;
		int max=a[0];
		for(int i=1;i<a.length;i++)
		{
			if(a[i]<=max)
			{
				maxDiff=Math.max(maxDiff,max-a[i]);
			}else
			{
				max=a[i];
			}
		}
		return maxDiff;
	}
	
	public static getTestArray(int n)
	{
		if(n<=0)
		{
			return null;
		}
		int[] arr=new int[n];
		Random rnd=new Random();
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=rnd.nextInt(1001);
		}
	}
	public static void main(String[] args)
	{
		Random rnd=new Random();
		int[] inputArr=MaximumDifferenceSvc.getTestArray(rnd.nextInt(1001));
		System.out.println("input: " + Arrays.toString(inputArr));
		int maxDiff=MaximimumDifferenceSvc.findMaxDifference(inputArr);
		System.out.println("max difference: " + maxDiff);
	}
}

//O(N) time.

public static void finMaxDrop(int[] arr)
	{
		
		int minSofar = arr[0];
		int maxDrop = 0;
		
		for(int i = 1 ; i < arr.length ; i++)
		{
			if(arr[i] >  minSofar)
			{
				int currentDrop = arr[i] -  minSofar;
				
				maxDrop = Math.max(maxDrop,currentDrop);
				minSofar = Math.min(minSofar, arr[i]);
				
				
			}
			else{
				minSofar = Math.min(minSofar, arr[i]);
				
			}
			
		}
		
		
		System.out.println(maxDrop);
		
		
	}

Here is C++ solution.
Assumption is that max drop is the difference between two elements, m and n, where m < n.
There for the drop is expressed as negative number.

Running time is O(N).

#include <climits>
#include <iostream>
using namespace std;

//O(N) algorithm
int find_max_drop(int * input, int len)
{
	int min = INT_MAX;
	int max_pos = 0;

	for (int i = 1; i <len; i++)
	{
		int drop = input[i] - input[max_pos];
		if (drop < min)
			min = drop;
		if (input[max_pos] < input[i])
			max_pos = i;	
	}
	return min;	
}

int main()
{
	int input[6] = {5,3,4,1,6,7};
	int min = find_max_drop(input, 6);
	cout <<" max drop = " << min <<endl;
	return 1;
}

This can be done using dynamic programming.
Keep a max array of size n where each elelement of that array max[i] would be equal to the maximum element in the array from index i till n.
This array would be created using DP such that
Max[]

Javascript:

ns => {
    var maxDiff = -1;
    var curMax = -1;
    var i;
    for(i=0; i < ns.length; ++i) {
        if (curMax < ns[i]) {
            curMax = ns[i];
            continue;
        }
        maxDiff = Math.max(maxDiff, curMax - ns[i]);
    }
    return maxDiff;
}

functional solution:

ns => ns.reduce((m, n) => {
    return {
        curMax: Math.max(n, m.curMax),
        maxDiff: Math.max(m.maxDiff, m.curMax - n)
    }
}, {curMax: -1, maxDiff: -1}).maxDiff;

Max drop will be between two elements and one of them can be maximum or minimum of the array.

public class MaxDiff {
	
	public static int solution(int[] arr) {
		int maxIndex = 0;
		int minIndex = 0;
		if(arr.length < 2) return -1;
		for(int i = 1; i < arr.length; i++) {
			if(arr[i] > arr[maxIndex]) maxIndex = i;
			if(arr[i] < arr[minIndex]) minIndex = i;
		}
		
		if(minIndex > maxIndex) {
			return arr[minIndex] - arr[maxIndex];
		} else {
			int maxDiff = Integer.MIN_VALUE;
			for(int i = 0; i < minIndex;i++){
				if(arr[minIndex]-arr[i] > maxDiff) maxDiff = arr[i]- arr[minIndex];
			}
			
			for(int i = maxIndex+1; i< arr.length; i++) {
				if(arr[maxIndex]-arr[i] > maxDiff) maxDiff = arr[maxIndex] - arr[i];
			}
			return maxDiff;
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {1, 200, 2};
		System.out.println(solution(arr));
	}

}

Maximum drop will be two elements in the array, and one of them is either maximum or minimum in the array

public class MaxDiff {
	
	public static int solution(int[] arr) {
		int maxIndex = 0;
		int minIndex = 0;
		if(arr.length < 2) return -1;
		for(int i = 1; i < arr.length; i++) {
			if(arr[i] > arr[maxIndex]) maxIndex = i;
			if(arr[i] < arr[minIndex]) minIndex = i;
		}
		
		if(minIndex > maxIndex) {
			return arr[minIndex] - arr[maxIndex];
		} else {
			int maxDiff = Integer.MIN_VALUE;
			for(int i = 0; i < minIndex;i++){
				if(arr[minIndex]-arr[i] > maxDiff) maxDiff = arr[i]- arr[minIndex];
			}
			
			for(int i = maxIndex+1; i< arr.length; i++) {
				if(arr[maxIndex]-arr[i] > maxDiff) maxDiff = arr[maxIndex] - arr[i];
			}
			return maxDiff;
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {1, 200, 2};
		System.out.println(solution(arr));
	}

}

1.Think of series as curve, so max difference in a any curve will occur when maxima of curve is achieved.

1. Take the first difference in curve
2. Take the cumulative sum of first difference.
3.The highest positive change in curve will occur at a point when curve will be at max point of increasing series.
4. The highest of cumulative sum will give pointer to max sum.

a = [10, 9, 6, 11, 3, 4, 5]
def max_dip(a):
max_value = a[0]
max_diff = 0
for elm in a:
if max_value < elm:
max_value = elm
if max_diff < max_value - elm:
max_diff = max_value - elm
print max_diff

max_dip(a)

a = [10, 9, 6, 11, 3, 4, 5]
def max_dip(a):
    max_value = a[0]
    max_diff = 0
    for elm in a:
        if max_value < elm:
            max_value = elm
        if max_diff < max_value - elm:
            max_diff = max_value - elm
    print max_diff

max_dip(a)

a = [10, 9, 6, 11, 3, 4, 5]
def max_dip(a):
    max_value = a[0]
    max_diff = 0
    for elm in a:
        if max_value < elm:
            max_value = elm
        if max_diff < max_value - elm:
            max_diff = max_value - elm
    print max_diff

max_dip(a)

public static void max_dip(int[] arr){

int max=arr[0];
int diff=0;
for (int i=0; i<arr.length; i++)
{
if(diff < max - arr[i])
diff=max-arr[i];
if(max<arr[i])
max=arr[i];
System.out.println(max+" "+diff +" "+arr[i]);
}
if(diff > 0 )
System.out.println(diff);
else
System.out.println("No Drop");

}

I think the easiest way is to start from the end of the array and keep track of the minimum element seen so far (which will maximize the difference a[i] - min)

public static int maxDrop (int[] a) {
        int maxDrop = -1;
        int min = a[a.length - 1];

        for (int i = a.length - 2; i >= 0; i--) {
            if (a[i+1] < min) min = a[i+1];
            if (a[i] - min > maxDrop) maxDrop = a[i] - min;
        }

        return maxDrop;
    }

public static int maxDrop(int[] ar) {
    
    if(ar == null || ar.length == 0)
      return -1;
    
    int localDiff = 0;
    int cumulativeDiff = 0;
    int answer = 0;
    
    for(int i=0; i<ar.length-1; i++) {
      localDiff = ar[i] - ar[i+1];
      cumulativeDiff = cumulativeDiff + localDiff;
      answer = Math.max(answer, cumulativeDiff);
    }
    
    return answer;

}

public static int maxDrop(int[] ar) {
    
    if(ar == null || ar.length == 0)
      return -1;
    
    int localDiff = 0;
    int cumulativeDiff = 0;
    int answer = 0;
    
    for(int i=0; i<ar.length-1; i++) {
      localDiff = ar[i] - ar[i+1];
      cumulativeDiff = cumulativeDiff + localDiff;
      answer = Math.max(answer, cumulativeDiff);
    }
    
    return answer;    
  }

public static int maxDrop(int []array) {
		
		if(array == null || array.length < 2) {
			return -1;
		}
		
		int leastValInArray = array[0];
		int highestValInArray = array[1];
		if(array[0] > array[1]) {
			leastValInArray = array[1];
			highestValInArray = array[0];
		}
		
		int arrayLength = array.length;
		
		for(int i = 2;i<arrayLength;i++) {
			if(leastValInArray > array[i]) {
				leastValInArray = array[i];
			} 
			if(highestValInArray < array[i]) {
				highestValInArray = array[i];
			}
		}
		
		return highestValInArray - leastValInArray;
	}

Time Complexity : O(n-2) ;

public int biggestDropB(int[] a){
		int maxDifference = 0;
		for(int i = 0; i < a.length; i++){
			for(int j = i; j< a.length; j++){
				if(a[i] - a[j] < maxDifference){
					maxDifference = a[i] - a[j];
				}
			}
		}
		return maxDifference;

}

O(n) algo!!

int getMaxDrop( int[] arr ){
		if( arr.length < 2 ) return -1;
		int a = arr[0];
		int b = arr[1];
		int maxDrop = (a >= b ? a-b : -1);

		for( int i = 2; i < arr.length; i++){
			if(arr[i] > a){
				a = arr[i];
			}
			else if( arr[i] < b ){
				b = arr[i];
				maxDrop = Math.max(maxDrop, a-b);
			}
		}
		return  maxDrop;
	}

function maximumDrop(arr) {
    var maxDiff = -1;
    var max = arr[arr.length - 1];
    var min = max;

    for (var i = arr.length - 1; i >= 0; i--) {
        if (arr[i] > max) {
            max = arr[i];
            var newDiff = max - min;            
            maxDiff = maxDiff < newDiff ? newDiff : maxDiff;
        }

        if (arr[i] < min) {
            max = arr[i];
            min = arr[i];
        }
    }

    console.log(maxDiff);
}

maximumDrop([4, 670, 1200, 340, 220, 4300])

def max_drop(numbers):
    max_diff = 0
    max_num = numbers[0]
    for num in numbers:
        diff = max_num - num
        if diff > max_diff:
            max_diff = diff
        if num > max_num:
            max_num = num
    return max_diff

Using a modified version of Kadane's Algorithm
O(n) time, O(1) space

public static int maxDrop(int[] input) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int i = 0; i < input.length - 1 ; i++) {
			maxEndingHere = maxEndingHere + input[i] - input[i + 1];
			if (maxEndingHere < 0) maxEndingHere = 0;
			if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
		}
		 return maxSoFar;
	}

DP solution:

def max_drop_dp(arr, max_drop, max_elm, i):
    if i == len(arr):
        return max_drop
    return max_drop_dp(arr, max(max_drop, max_elm - arr[i]), max(max_elm, arr[i]), i + 1)

def max_drop_dp_wrapper(arr):
    return max_drop_dp(arr, -float('inf'), arr[0], 1)

public static int maxDrop(int [] numarr){
if(numarr.length < 2)
return 0;
int max = numarr[0];
int diff = 0;
for(int i = 0; i < numarr.length; i++){
if(max < numarr[i])
max = numarr[i];
if(max - numarr[i] > diff)
diff = max - numarr[i];
}
return diff;
}

JavaScript Solution O(n) solution.

function getBiggestDrop(numbers) {
    var i;
    var drop;
    var maxDrop = 0;

    for (i = 0; i < numbers.length - 1; i++) {
        drop = numbers[i] - numbers[i+1];
        if (drop > maxDrop) {
            maxDrop = drop;
        }
    }

    return maxDrop;
}

def find_max_delta(input_array):
max_delta = 0
front = 0
back = len(input_array) - 1
while front < back:
f_delta = abs(input_array[front] - input_array[front+1])
b_delta = abs(input_array[back] - input_array[back-1])

if f_delta > max_delta:
max_delta = f_delta
if b_delta > max_delta:
max_delta = b_delta

front += 1
back -= 1
return max_delta


def main():
input_array = [1, 2, 32, 452, 6, -200, 10, 0]
output = find_max_delta(input_array)
print output

Heres mine, O(n/2)

def find_max_delta(input_array):
    max_delta = 0
    front = 0
    back = len(input_array) - 1
    while front < back:
        f_delta = abs(input_array[front] - input_array[front+1])
        b_delta = abs(input_array[back] - input_array[back-1])

        if f_delta > max_delta:
            max_delta = f_delta
        if b_delta > max_delta:
            max_delta = b_delta

        front += 1
        back -= 1
    return max_delta


def main():
    input_array = [1, 2, 32, 452, 6, -200, 10, 0]
    output = find_max_delta(input_array)
    print output

private static int GetMaximumDropBetweenTwoArrayElementsGivenTheSecondElementComesAfterTheFirstOne(int[] a) {
        int min = a[0], max=a[0], drop = Integer.MIN_VALUE;
        for (int i = 1; i < a.length; i++) {
            if (a[i] > max)      min = max = a[i];
            else if (a[i] < min) min = a[i];
            drop = Math.max(drop, max-min);
        }
        return drop;
    }

Notice than when moving from k to k + 1 the value of M[k] = max (a[k], a[k + 1], a[k + 2], ...) could either remain the same, or could decrease if a[k] is that max element. If it is the case, we need to find new max element among a[k + 1], a[k + 2], ...

To avoid doing linear search every time we can have some data structure that keeps elements in sorted order and yields a max element efficiently. Also it has to support remove(x) operation efficiently. A balanced binary search tree with could do. It provides log n performance for both max() and remove(x) operations.

The algorithm:
1. Add all array elements to the tree T // n log n
2. Let MAX_DROP = Integer.MIN_VALUE.
2. Let k = 0.
3. Search and remove value a[k] from T. // log n
4. Let CUR_MAX be of remaining elements in T. // log n
5. Let CUR_DROP = CUR_MAX - a[k]
6. If (CUR_DROP > MAX_DROP) MAX_DROP := CUR_DROP;
7. k := k + 1
8. Repeat starting from 2 while k <= n - 2.
9. Return MAX_DROP.

The time complexity of this algorithm is O(n log n) worst case. The space complexity is O(n).

In case input array contains duplicate elements the algorithm above needs to be modified. We need to keep in tree T number of occurrences of each element. So essentially it will be multi-set (a bag). The remove(x) operation should decrement count in the node, and remove it from tree only if the count becomes 0.

if (A.size() < 2 ) // bad case... or leave this out and let method return -1

minSoFar=A[0];
maxDiffSoFar=-1;

for (int i=1; i < A.size(); i++)
{
	maxDiffSoFar = MAX( maxDiffSoFar , A[i] - minSoFar );
	minSoFar = MIN ( minSoFar, A[i] );
}

// returns -1 to signal integer array completely decreasing
return maxDiffSoFar;

//Fixed a bug and will run in O(n)

@Test
	public void testMaxDifferenceInNumbers() {
		int[] A = new int[]{600,56,70,99,200,340,19,39,78,99,400,2};
		
		if (A.length < 2 )
			fail();

		int minSoFar = A[0];
		int maxSoFar = A[0];
		int maxDiffSoFar = -1;

		for (int i=1; i < A.length; i++)
		{
			maxSoFar = Math.max(maxSoFar, A[i]);
			minSoFar = Math.min(minSoFar, A[i]);
			maxDiffSoFar = Math.max(maxDiffSoFar, Math.abs(maxSoFar - minSoFar));
		}

		System.out.println("Max diff is : " + maxDiffSoFar);
	}

Output: Max diff is : 598