A subsequence X[1..k] is nice if X[i] > X[i - 2] for all i > 2. Compute a longest nice subsequence of an arbitrary array of integers A[1...n].
I have some confusions regarding this problem statement as no examples were provided.
I took an example array : A = { 1,2,3,4,2,-1,0,7,9}.
I did the Comparison of elements in an iterative way : 3 > 1, include 3 in the output array.
4 > 2, include 4, and so on.
From my understanding of this problem, I figured out this Nice Subsequence: {3,4,7,9}.
I am confused that if the subsequence consists of elements 1 and 2 in it, because I think {1,2,3,4,7,9} is also valid. I need to clear this confusion.
Any help is much appreciated.
Below there is my written Java code.
public static int niceSub(int[] input) {
int n = input.length;
int i, j;
int[] X = new int[n];
for (i = 0; i < n; i++) {
X[i] = 0;
}
ArrayList<Integer> answer = new ArrayList<>();
int[] A = new int[n + 1];
A[0] = 0;
for (i = 1; i <= n; i++) {
A[i] = input[i - 1];
}
for (i = 3; i < A.length; i++) {
for (j = i - 2; j <= i - 2; j++) {
if (A[i] > A[j]) {
answer.add(A[i]);
}
}
}
System.out.println(answer);
// System.out.println(Arrays.toString(X));
return answer.size();
}