NIce Subsequence - A variant of Longest Increasing Subsequence

452 views Asked by At

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();
    }
0

There are 0 answers