Java Solution using LCS


#1
       public int lis(final int[] A) {
    TreeSet<Integer>temp=new TreeSet<>();
    int i,j,n=A.length;
    for(i=0;i<n;i++)
        temp.add(A[i]);
    Iterator<Integer> itr=temp.iterator();
    int B[]=new int[temp.size()];
    i=0;
    while(itr.hasNext())
        B[i++]=itr.next();
    int m=temp.size();
    int dp[][]=new int[m+1][n+1];
    for(i=0;i<=m;i++){
        for(j=0;j<=n;j++){
            if(i==0 || j==0) dp[i][j]=0;
            else if(B[i-1]==A[j-1]) dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[m][n];
}