Find the length of a longest contained range
LongestContainedRange.javapublic static int longestContainedRange(List<Integer> A) {
// unprocessedEntries records the existence of each entry in A.
Set<Integer> unprocessedEntries = new HashSet<>();
for (int i = 0 ; i < A.size(); i++) {
unprocessedEntries.add(A.get(i));
}
int maxIntervalSize = 0;
for (int i = 0; i < A.size(); i++) {
if (unprocessedEntries.contains(A.get(i))) {
unprocessedEntries.remove(A.get(i));
// Finds the lower bound of the largest range containing a.
int lowerBound = A.get(i) - 1;
while (unprocessedEntries.contains(lowerBound)) {
unprocessedEntries.remove(lowerBound);
--lowerBound;
}
// Finds the upper bound of the largest range containing a.
int upperBound = A.get(i) + 1;
while (unprocessedEntries.contains(upperBound)) {
unprocessedEntries.remove(upperBound);
++upperBound;
}
maxIntervalSize = Math.max(upperBound - lowerBound - 1,
maxIntervalSize);
}
}
return maxIntervalSize;
}
Solution 2:
public static Pair<Integer, Integer>
findLongestContainedRange(List<Integer> A) {
// S records the existence of each entry in A.
Set<Integer> S = new HashSet<>();
for (int a : A) {
S.add(a);
}
int maxLen = 0;
Pair<Integer, Integer> maxRange = new Pair<>(0, -1);
// L stores the longest length ending at each A[i].
Map<Integer, Integer> L = new HashMap<>();
for (int a : A) {
int len = longestRangeLen(a, S, L);
if (len > maxLen) {
maxLen = len;
maxRange = new Pair<>(a - len + 1, a);
}
}
return maxRange;
}
private static int longestRangeLen(int a, Set<Integer> S,
Map<Integer, Integer> L) {
// Base case. If a does not exist.
if (!S.contains(a)) {
return 0;
}
if (!L.containsKey(a)) {
L.put(a, longestRangeLen(a - 1, S, L) + 1);
}
return L.get(a);
}
