Solution: Longest Palindromic Subsequence

using System;
class Program
{
    /// <summary>
    /// Finds the length of the longest palindromic subsequence.
    /// </summary>
    /// <param name="s">Input string.</param>
    /// <param name="startIndex">Starting index of the sequence.</param>
    /// <param name="endIndex">Ending index of the sequence.</param>
    /// <returns>Length of longest palindromic subsequence.</returns>
    static int LongestPalindromicSubsequenceRecursive(string s, int startIndex, int endIndex)
    {
        if (startIndex > endIndex)
            return 0;
        // Every sequence with one element is a palindrome of length 1
        if (startIndex == endIndex)
            return 1;
        // Case 1: elements at the beginning and the end are the same
        if (s[startIndex] == s[endIndex])
            return 2 + LongestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex - 1);
        // Case 2: skip one element either from the beginning or the end
        int c1 = LongestPalindromicSubsequenceRecursive(s, startIndex + 1, endIndex);
        int c2 = LongestPalindromicSubsequenceRecursive(s, startIndex, endIndex - 1);
        return Math.Max(c1, c2);
    }
    /// <summary>
    /// Finds the length of the longest palindromic subsequence.
    /// </summary>
    /// <param name="s">Input string.</param>
    /// <returns>Length of longest palindromic subsequence.</returns>
    static int LongestPalindromicSubsequence(string s)
    {
        return LongestPalindromicSubsequenceRecursive(s, 0, s.Length - 1);
    }
    // Driver code to test the above method
    static void Main(string[] args)
    {
        Console.WriteLine(LongestPalindromicSubsequence("cddpd"));
        Console.WriteLine(LongestPalindromicSubsequence("abdbca"));
        Console.WriteLine(LongestPalindromicSubsequence("cddpd"));
        Console.WriteLine(LongestPalindromicSubsequence("pqr"));
    }
}