Dada una secuencia, encuentre la longitud de la subsecuencia palindrómica más larga en ella. 
Ejemplos:
Input : abbaab Output : 4 Input : geeksforgeeks Output : 5
Hemos discutido una solución de programación dinámica para la subsecuencia palindrómica más larga que se basa en la siguiente fórmula recursiva.
C++
// A Space optimized Dynamic Programming based C++
// program for LPS problem
#include <bits/stdc++.h>
using namespace std;
// Returns the length of the longest palindromic
// subsequence in str
int lps(string &s)
{
int n = s.length();
// a[i] is going to store length of longest
// palindromic subsequence of substring s[0..i]
int a[n];
// Pick starting point
for (int i = n - 1; i >= 0; i--) {
int back_up = 0;
// Pick ending points and see if s[i]
// increases length of longest common
// subsequence ending with s[j].
for (int j = i; j < n; j++) {
// similar to 2D array L[i][j] == 1
// i.e., handling substrings of length
// one.
if (j == i)
a[j] = 1;
// Similar to 2D array L[i][j] = L[i+1][j-1]+2
// i.e., handling case when corner characters
// are same.
else if (s[i] == s[j])
{
// value a[j] is depend upon previous
// unupdated value of a[j-1] but in
// previous loop value of a[j-1] is
// changed. To store the unupdated
// value of a[j-1] back_up variable
// is used.
int temp = a[j];
a[j] = back_up + 2;
back_up = temp;
}
// similar to 2D array L[i][j] = max(L[i][j-1],
// a[i+1][j])
else
{
back_up = a[j];
a[j] = max(a[j - 1], a[j]);
}
}
}
return a[n - 1];
}
/* Driver program to test above functions */
int main()
{
string str = "GEEKSFORGEEKS";
cout << lps(str);
return 0;
}
Java
// A Space optimized Dynamic Programming
// based Java program for LPS problem
class GFG {
// Returns the length of the longest
// palindromic subsequence in str
static int lps(String s)
{
int n = s.length();
// a[i] is going to store length
// of longest palindromic subsequence
// of substring s[0..i]
int a[] = new int[n];
// Pick starting point
for (int i = n - 1; i >= 0; i--)
{
int back_up = 0;
// Pick ending points and see if s[i]
// increases length of longest common
// subsequence ending with s[j].
for (int j = i; j < n; j++) {
// similar to 2D array L[i][j] == 1
// i.e., handling substrings of length
// one.
if (j == i)
a[j] = 1;
// Similar to 2D array L[i][j] = L[i+1][j-1]+2
// i.e., handling case when corner characters
// are same.
else if (s.charAt(i) == s.charAt(j))
{
int temp = a[j];
a[j] = back_up + 2;
back_up = temp;
}
// similar to 2D array L[i][j] = max(L[i][j-1],
// a[i+1][j])
else
{
back_up = a[j];
a[j] = Math.max(a[j - 1], a[j]);
}
}
}
return a[n - 1];
}
/* Driver program to test above functions */
public static void main(String[] args)
{
String str = "GEEKSFORGEEKS";
System.out.println(lps(str));
}
}
//This article is contributed by prerna saini.
Python3
# A Space optimized Dynamic Programming # based Python3 program for LPS problem # Returns the length of the longest # palindromic subsequence in str def lps(s): n = len(s) # a[i] is going to store length # of longest palindromic subsequence # of substring s[0..i] a = [0] * n # Pick starting point for i in range(n-1, -1, -1): back_up = 0 # Pick ending points and see if s[i] # increases length of longest common # subsequence ending with s[j]. for j in range(i, n): # similar to 2D array L[i][j] == 1 # i.e., handling substrings of length # one. if j == i: a[j] = 1 # Similar to 2D array L[i][j] = L[i+1][j-1]+2 # i.e., handling case when corner characters # are same. elif s[i] == s[j]: temp = a[j] a[j] = back_up + 2 back_up = temp # similar to 2D array L[i][j] = max(L[i][j-1], # a[i+1][j]) else: back_up = a[j] a[j] = max(a[j - 1], a[j]) return a[n - 1] # Driver Code string = "GEEKSFORGEEKS" print(lps(string)) # This code is contributed by Ansu Kumari.
C#
// A Space optimized Dynamic Programming
// based C# program for LPS problem
using System;
class GFG {
// Returns the length of the longest
// palindromic subsequence in str
static int lps(string s)
{
int n = s.Length;
// a[i] is going to store length
// of longest palindromic subsequence
// of substring s[0..i]
int []a = new int[n];
// Pick starting point
for (int i = n - 1; i >= 0; i--)
{
int back_up = 0;
// Pick ending points and see if s[i]
// increases length of longest common
// subsequence ending with s[j].
for (int j = i; j < n; j++) {
// similar to 2D array L[i][j] == 1
// i.e., handling substrings of length
// one.
if (j == i)
a[j] = 1;
// Similar to 2D array L[i][j] = L[i+1][j-1]+2
// i.e., handling case when corner characters
// are same.
else if (s[i] == s[j])
{
int temp = a[j];
a[j] = back_up + 2;
back_up = temp;
}
// similar to 2D array L[i][j] = max(L[i][j-1],
// a[i+1][j])
else
{
back_up = a[j];
a[j] = Math.Max(a[j - 1], a[j]);
}
}
}
return a[n - 1];
}
// Driver program
public static void Main()
{
string str = "GEEKSFORGEEKS";
Console.WriteLine(lps(str));
}
}
// This code is contributed by vt_m.
PHP
<?php
// A Space optimized Dynamic
// Programming based PHP
// program for LPS problem
// Returns the length of
// the longest palindromic .
// subsequence in str
function lps($s)
{
$n = strlen($s);
// Pick starting point
for ($i = $n - 1;
$i >= 0; $i--)
{
$back_up = 0;
// Pick ending points and
// see if s[i] increases
// length of longest common
// subsequence ending with s[j].
for ($j = $i; $j < $n; $j++)
{
// similar to 2D array
// L[i][j] == 1 i.e.,
// handling substrings
// of length one.
if ($j == $i)
$a[$j] = 1;
// Similar to 2D array
// L[i][j] = L[i+1][j-1]+2
// i.e., handling case when
// corner characters are same.
else if ($s[$i] == $s[$j])
{
// value a[j] is depend
// upon previous unupdated
// value of a[j-1] but in
// previous loop value of
// a[j-1] is changed. To
// store the unupdated value
// of a[j-1] back_up variable
// is used.
$temp = $a[$j];
$a[$j] = $back_up + 2;
$back_up = $temp;
}
// similar to 2D array
// L[i][j] = max(L[i][j-1],
// a[i+1][j])
else
{
$back_up = $a[$j];
$a[$j] = max($a[$j - 1],
$a[$j]);
}
}
}
return $a[$n - 1];
}
// Driver Code
$str = "GEEKSFORGEEKS";
echo lps($str);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// A Space optimized Dynamic Programming
// based Python3 program for LPS problem
// Returns the length of the longest
// palindromic subsequence in str
function lps(s){
let n = s.length
// a[i] is going to store length
// of longest palindromic subsequence
// of substring s[0..i]
let a = new Array(n).fill(0);
// Pick starting point
for(let i = n - 1; i >= 0; i--){
let back_up = 0
// Pick ending points and see if s[i]
// increases length of longest common
// subsequence ending with s[j].
for (let j = i; j < n; j++){
// similar to 2D array L[i][j] == 1
// i.e., handling substrings of length
// one.
if(j == i)
a[j] = 1
// Similar to 2D array L[i][j] = L[i+1][j-1]+2
// i.e., handling case when corner characters
// are same.
else if(s[i] == s[j]){
let temp = a[j]
a[j] = back_up + 2
back_up = temp
}
// similar to 2D array L[i][j] = max(L[i][j-1],
// a[i+1][j])
else{
back_up = a[j]
a[j] = Math.max(a[j - 1], a[j])
}
}
}
return a[n - 1]
}
// Driver Code
let string = "GEEKSFORGEEKS"
document.write(lps(string),"</br>")
// This code is contributed by shinjanpatra
</script>
Publicación traducida automáticamente
Artículo escrito por bibhudhendra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA