Problem with Longest Increasing Subsequence Algorithm

[Avantika_Sharmaa24]

Hello,

I am having trouble with the Longest Increasing Subsequence algorithm. I am using the code from this resource to try to get the longest increasing subsequence. However, the output is not what I am expecting.

Code:

public static int lis(final int[] A)
    {
        int n = A.length;
        int[] dp = new int[n];
        int maxlen = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] = 1;
            for (int j = 0; j < i; j++)
            {
                if (A[i] > A[j] && dp[i] < dp[j] + 1)
                    dp[i] = dp[j] + 1;
            }
            maxlen = Math.max(maxlen, dp[i]);
        }
        return maxlen;
    }

I would appreciate any help in resolving this issue.

Thanks.

[gulshan212]

Well, I searched for it on Google and I found that there are some logical error including some other issue with your code.
Try this code to get the desire result.

Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public static List<Integer> findLIS(int[] A) {
    int n = A.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int maxlen = 1;
    int endIndex = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (A[i] > A[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
                if (dp[i] > maxlen) {
                    maxlen = dp[i];
                    endIndex = i;
                }
            }
        }
    }

    List<Integer> lis = new ArrayList<>();
    lis.add(A[endIndex]);

    for (int i = endIndex - 1; i >= 0; i--) {
        if (A[i] < A[endIndex] && dp[i] == dp[endIndex] - 1) {
            lis.add(A[i]);
            endIndex = i;
        }
    }

    Collections.reverse(lis);
    return lis;
}

Thanks