Longest palindromic subsequence

def longest_pal_subseq(s):
    n = len(s)
    nxt = [0] * n                        # row i + 1 of the table
    for i in range(n - 1, -1, -1):
        cur = [0] * n
        cur[i] = 1                       # a single character
        for j in range(i + 1, n):
            if s[i] == s[j]:
                cur[j] = 2 + (nxt[j - 1] if i + 1 <= j - 1 else 0)
            else:
                cur[j] = max(nxt[j], cur[j - 1])
        nxt = cur
    return nxt[n - 1]

#include <algorithm>
#include <string>
#include <vector>

int solve(std::string s) {
    const int n = s.size();
    std::vector<int> nxt(n, 0), cur(n, 0);          // rows i + 1 and i
    for (int i = n - 1; i >= 0; --i) {
        std::fill(cur.begin(), cur.end(), 0);
        cur[i] = 1;
        for (int j = i + 1; j < n; ++j)
            cur[j] = s[i] == s[j] ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : std::max(nxt[j], cur[j - 1]);
        std::swap(nxt, cur);
    }
    return nxt[n - 1];
}

class Solution {
    public int longestPalSubseq(String s) {
        int n = s.length();
        int[] nxt = new int[n], cur = new int[n];        // rows i + 1 and i
        for (int i = n - 1; i >= 0; i--) {
            java.util.Arrays.fill(cur, 0);
            cur[i] = 1;
            for (int j = i + 1; j < n; j++)
                cur[j] = s.charAt(i) == s.charAt(j) ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : Math.max(nxt[j], cur[j - 1]);
            int[] t = nxt; nxt = cur; cur = t;
        }
        return nxt[n - 1];
    }
}

function longestPalSubseq(s) {
  const n = s.length;
  let nxt = new Array(n).fill(0);          // row i + 1
  for (let i = n - 1; i >= 0; i--) {
    const cur = new Array(n).fill(0);
    cur[i] = 1;
    for (let j = i + 1; j < n; j++)
      cur[j] = s[i] === s[j] ? 2 + (i + 1 <= j - 1 ? nxt[j - 1] : 0) : Math.max(nxt[j], cur[j - 1]);
    nxt = cur;
  }
  return nxt[n - 1];
}

fn solve(s: &str) -> i64 {
    let c: Vec<u8> = s.bytes().collect();
    let n = c.len();
    let mut nxt = vec![0i64; n];                        // row i + 1
    for i in (0..n).rev() {
        let mut cur = vec![0i64; n];
        cur[i] = 1;
        for j in i + 1..n {
            cur[j] = if c[i] == c[j] {
                2 + if i + 1 <= j - 1 { nxt[j - 1] } else { 0 }
            } else {
                nxt[j].max(cur[j - 1])
            };
        }
        nxt = cur;
    }
    nxt[n - 1]
}

import Data.Array

solve :: String -> Int
solve s = table ! (0, n - 1)
  where
    n = length s
    a = listArray (0, n - 1) s
    -- a lazy table: each interval refers only to shorter ones
    table = array ((0, 0), (n - 1, n - 1)) [((i, j), go i j) | i <- [0 .. n - 1], j <- [0 .. n - 1]] :: Array (Int, Int) Int
    go i j
      | i > j = 0
      | i == j = 1
      | a ! i == a ! j = 2 + (if i + 1 <= j - 1 then table ! (i + 1, j - 1) else 0)
      | otherwise = max (table ! (i + 1, j)) (table ! (i, j - 1))