As an input you have non-empty zero-indexed array of integers. The goal is to find the longest subsequence (any sequence obtained by removing some elements from A), where difference between min value and max value does not exceed 1.
For example, given array: 6,10,7,7,9,8 function should return 3, because 6,7,7 (or 7,7,8) is the longest qualifying subsequence.
Is this solution efficient?
public int solution(int[] A) {
Arrays.sort(A);
int counter = 0;
int res = 0;
int val = -1;
for (int i = 0; i < A.length - 1; i++) {
if (val == -1 && A[i + 1] - A[i] < 2) {
counter = 2;
val = A[i + 1] - A[i];
} else if (val == 0 && A[i + 1] - A[i] <= 1) {
counter++;
val = A[i + 1] - A[i];
} else if (val == 1 && A[i + 1] - A[i] == 0) {
counter++;
} else {
val = -1;
res = Math.max(res, counter);
counter = 0;
}
}
return res;
}
Time complexity is linearithmic.