SuprBay: The PirateBay Forum

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.

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

Avantika_Sharmaa24

gulshan212