Longest Palindromic Subsequence Print

#include<bits/stdc++.h>

using namespace std;

int main()

{

    string s;

    cout << "Enter String :: ";

    cin >> s;

    int n = s.size();

    int dp[n][n];

    for(int i=0; i<n; i++)

    {

        for(int j=0; j<n; j++)

        {

            if(i == j)

                dp[i][j] = 1;

            else

                dp[i][j] = 0;

        }

    }

    for(int k=1; k<n; k++)

    {

        for(int i=0; i+k<n; i++)

        {

            int j = i + k;

            if(s[i] == s[j])

                dp[i][j] = dp[i+1][j-1] + 2;

            else

                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);

        }

    }

    int ln = dp[0][n-1];

    char str[ln];

    str[ln] = '\0';

    int start = 0, finish = ln-1;

    int i = 0, j = n-1;

    while(start < finish)

    {

        if(s[i] == s[j])

        {

            str[start] = s[i];

            str[finish] = s[i];

            start++, finish--;

            i++, j--;

        }

        else if(dp[i+1][j] > dp[i][j-1])

            i++;

        else

            j--;

    }

    if(start == finish)

        str[i] = s[i];

    cout << "Longest Palindromic Subsequence Size :: " << ln << "\n";

    cout << "Longest Palindromic Subsequence :: " << str << "\n";

    return 0;

}