LPS.java

import java.util.Scanner;

public class LPS
{
    public static int LCS(int[] seq, int[] rev, int n)
    {
        int[][] dp = new int[n + 1][n + 1];

        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(seq[i - 1] == rev[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[n][n];
    }

    public static void main(String[] args)
    {
        int n;
        Scanner data = new Scanner(System.in);
        System.out.println("Enter the value of integer n: ");
        n = data.nextInt();

        if(1 <= n && n <= 100)
        {
            int[] seq = new int[n];
            System.out.println("Enter the sequence: ");
            for(int i = 0; i < n; i++)
            {
                seq[i] = data.nextInt();
            }

            int[] rev = new int[n];
            for(int i = 0; i < n; i++)
            {
                rev[i] = seq[n - i - 1];
            }

            int lpsLength = LCS(seq, rev, n);
            System.out.println("The length of the Longest Palindromic Subsequence is: " + lpsLength);
        }
        else
        {
            System.out.println("Value of n should be between 1 and 100.");
        }

    }
}