Longest Palindromic Subsequence

/*
 * Problem : Process text.
 * Input   : One line of text.
 * Output  : The length.
 * Approach: Interval DP.
 * Time    : O(n^2)
 * Space   : O(n^2)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String s) {
        // Step 1: best[i][j] = the longest palindromic subsequence inside s[i..j].
        int n = s.length();
        int[][] best = new int[n][n];

        // Step 2: Go from the last row to the first, so the smaller parts are ready when we need them.
        for (int i = n - 1; i >= 0; i--) {
            best[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // Step 3: Equal outer letters add 2 to the best of the inside part.
                    best[i][j] = (i + 1 <= j - 1 ? best[i + 1][j - 1] : 0) + 2;
                } else {
                    // Step 4: Otherwise drop the left letter or the right letter and take the better result.
                    best[i][j] = Math.max(best[i + 1][j], best[i][j - 1]);
                }
            }
        }
        return best[0][n - 1];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}