Uva 11151 Solution

#include<bits/stdc++.h>
using namespace std;
int lcs(string s)
{
    int n = s.size(), i, j, k, L[n][n];

    for(i=0;i<n;i++)
        L[i][i] = 1;

    for(k=2;k<=n;k++)
    {
        for(i=0;i<n-k+1;i++)
        {
            j = i+k-1;

            if(s[i] == s[j] && k == 2)
                L[i][j] = 2;

            else if(s[i] == s[j])
                L[i][j] = L[i+1][j-1] + 2;

            else
                L[i][j] = max(L[i][j-1], L[i+1][j]);
        }
    }

    return L[0][n-1];
}
int main()
{
    int t;
    cin >> t;
    getchar();
    while(t--)
    {
        string s;
        getline(cin, s);
        if(s.empty())
        {
            cout << 0 << "\n";
            continue;
        }
        cout << lcs(s) << "\n";
    }
    return 0;
}