Longest Palindromic Subsequence

LPS.java

package kata;

public class LPS {

    public static int lps(char[] ch, int i, int j) {

        // Base Case 1: If there is only 1 character
        if (i == j) {
            return 1;
        }

        // Base Case 2: If there are only 2 characters and both are same
        if (ch[i] == ch[j] && i + 1 == j) {
            return 2;
        }

        if (ch[i] == ch[j]) {
            return 2 + lps(ch, i + 1, j - 1);
        }
        else {
            return Math.max(lps(ch, i, j - 1), lps(ch, i + 1, j));
        }

    }

    public static void main(String args[]) {

        System.out.println(lps("abca".toCharArray(), 0, 3));
    }
}