Max Difference - Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package org.fabri1983.maxdifference; | |
import java.util.Arrays; | |
import java.util.List; | |
/** | |
* Given an array of integers, compute the maximum difference between any item | |
* and any lower indexed smaller item for all the possible pairs. | |
* In other words, for the array arr, find the maximum value arr[j] - arr[i] | |
* for all i,j where 0 <= i < j < n and arr[i] < arr[j]. | |
* If no item has a smaller item with lower index, then return -1. | |
* | |
* For example, given arr = [1, 2, 6, 4], first compare 2 to the elements to its left. | |
* 1 is smaller, so calculate the difference 2 - 1 = 1. | |
* 6 is bigger than 2 and 1, so calculate the difference 6 - 2 = 4 and 6 - 1 = 5. | |
* The last element, 4, is only bigger than 2 and 1, and the differences are 4 - 2 = 2 and 4 - 1 = 3. | |
* The largest difference is 6 - 1 = 5. | |
*/ | |
public class MaxDifferenceMain { | |
public static void main(String[] args) { | |
List<Integer> case0 = Arrays.asList( | |
Integer.valueOf(2), | |
Integer.valueOf(3), | |
Integer.valueOf(10), | |
Integer.valueOf(2), | |
Integer.valueOf(4), | |
Integer.valueOf(8), | |
Integer.valueOf(1) | |
); | |
List<Integer> case1 = Arrays.asList( | |
Integer.valueOf(7), | |
Integer.valueOf(9), | |
Integer.valueOf(5), | |
Integer.valueOf(6), | |
Integer.valueOf(3), | |
Integer.valueOf(2) | |
); | |
int maxDifference0 = maxDifference(case0); | |
System.out.println(maxDifference0); | |
int maxDifference1 = maxDifference(case1); | |
System.out.println(maxDifference1); | |
} | |
public static int maxDifference(List<Integer> arr) { | |
// is everything ok? | |
if (!satisfyConditions(arr)) { | |
return invalidResult(); | |
} | |
// assume first element is the smaller one | |
int minimum = getFirstElement(arr); | |
// asume there is no max difference value | |
int maxDifference = invalidResult(); | |
int i = startingIndex(arr); | |
int end = endingIndex(arr); | |
while (continuationFunction(i, end)) { | |
int currentNumber = getCurrentElement(arr, i); | |
maxDifference = maximizeFunction(minimum, maxDifference, currentNumber); | |
minimum = minimizeFunction(minimum, currentNumber); | |
i = advanceIndex(i); | |
} | |
return setupResult(maxDifference); | |
} | |
private static int setupResult(int maxDifference) { | |
return maxDifference > 0 ? maxDifference : invalidResult(); | |
} | |
private static int minimizeFunction(int minimum, int currentNumber) { | |
return Math.min(minimum, currentNumber); | |
} | |
private static int maximizeFunction(int minimum, int maxDifference, int currentNumber) { | |
return Math.max(maxDifference, currentNumber - minimum); | |
} | |
private static int startingIndex(List<Integer> arr) { | |
return 1; | |
} | |
private static int endingIndex(List<Integer> arr) { | |
return arr.size(); | |
} | |
private static boolean continuationFunction(int i, int c) { | |
return i < c; | |
} | |
private static int advanceIndex(int i) { | |
return i + 1; | |
} | |
private static Integer getFirstElement(List<Integer> arr) { | |
return arr.get(0).intValue(); | |
} | |
private static int getCurrentElement(List<Integer> arr, int i) { | |
Integer numberBoxed = arr.get(i); | |
int currentNumber = numberBoxed.intValue(); | |
return currentNumber; | |
} | |
private static int invalidResult() { | |
return -1; | |
} | |
private static boolean satisfyConditions(List<Integer> list) { | |
return !isNullOrEmpty(list) && | |
hasMinimumSize(list) && | |
noNulls(list); | |
} | |
private static boolean hasMinimumSize(List<Integer> list) { | |
return endingIndex(list) >= 2; | |
} | |
private static boolean isNullOrEmpty(List<Integer> list) { | |
return list == null || list.isEmpty(); | |
} | |
private static boolean noNulls(List<Integer> list) { | |
for(Integer i : list) { | |
if (i == null) { | |
return false; | |
} | |
} | |
return true; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment