Longest palindromic subsequence using dynamic programming

Here given code implementation process.

/*
    C program for
    Longest palindromic subsequence using dynamic programming
*/
#include <stdio.h>
#include <string.h>

// Returns the max value of given two numbers
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
int findLPS(char *text)
{
	int n = strlen(text);
	if (n == 0)
	{
		return 0;
	}
	int dp[n][n];
	// Set 1 to all diagonal elements
	for (int i = 0; i < n; ++i)
	{
		dp[i][i] = 1;
	}
	for (int k = 2; k <= n; ++k)
	{
		for (int i = 0; i < n - k + 1; ++i)
		{
			int j = (k + i) - 1;
			if (k == 2 && text[i] == text[j])
			{
				// First similar pair
				dp[i][j] = 2;
			}
			else if (text[i] == text[j])
			{
				// Calculate sum the bottom left element + 2
				dp[i][j] = dp[i + 1][j - 1] + 2;
			}
			else
			{
				// When element are not same (i and j location)
				// Then change current element by max of 
                // left and down element
				dp[i][j] = maxValue(dp[i][j - 1], dp[i + 1][j]);
			}
		}
	}
	return dp[0][n - 1];
}
int main(int argc, char
	const *argv[])
{
	char *text1 = "pewmoozdp";
	char *text2 = "xbfdsafx";
	char *text3 = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	int ans = findLPS(text1);
	printf("\n Given  : %s ", text1);
	printf("\n Result : %d", ans);
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = findLPS(text2);
	printf("\n Given  : %s ", text2);
	printf("\n Result : %d", ans);
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = findLPS(text3);
	printf("\n Given  : %s ", text3);
	printf("\n Result : %d", ans);
	return 0;
}

Output

 Given  : pewmoozdp
 Result : 4
 Given  : xbfdsafx
 Result : 5
 Given  : abbisstiwebaccess
 Result : 8
// Java program for
// Longest palindromic subsequence using dynamic programming
public class Subsequence
{
	// Returns the max value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int findLPS(String text)
	{
		int n = text.length();
		if (n == 0)
		{
			return 0;
		}
		int[][] dp = new int[n][n];
		// Set 1 to all diagonal elements
		for (int i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		for (int k = 2; k <= n; ++k)
		{
			for (int i = 0; i < n - k + 1; ++i)
			{
				int j = (k + i) - 1;
				if (k == 2 && text.charAt(i) == text.charAt(j))
				{
					// First similar pair
					dp[i][j] = 2;
				}
				else if (text.charAt(i) == text.charAt(j))
				{
					// Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i][j] = maxValue(dp[i][j - 1], dp[i + 1][j]);
				}
			}
		}
		return dp[0][n - 1];
	}
	public static void main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text1 = "pewmoozdp";
		String text2 = "xbfdsafx";
		String text3 = "abbisstiwebaccess";
		// Test A
		// Text = pewmoozdp
		// "poop" is resultant palindrome
		// Length 4
		int ans = task.findLPS(text1);
		System.out.print("\n Given : " + text1);
		System.out.print("\n Result : " + ans);
		// Test B
		// Text = xbfdsafx
		// [xfsfx,xfdfx,xfafx] is resultant palindrome
		// Length 5
		ans = task.findLPS(text2);
		System.out.print("\n Given : " + text2);
		System.out.print("\n Result : " + ans);
		// Test C
		// Text = "abbisstiwebaccess"
		// [abissiba] is resultant palindrome
		// Length 8
		ans = task.findLPS(text3);
		System.out.print("\n Given : " + text3);
		System.out.print("\n Result : " + ans);
	}
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
// Include header file
#include <iostream>
#include <string>

using namespace std;
// C++ program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
	public:
		// Returns the max value of given two numbers
		int maxValue(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			return b;
		}
	int findLPS(string text)
	{
		int n = text.length();
		if (n == 0)
		{
			return 0;
		}
		int dp[n][n];
		// Set 1 to all diagonal elements
		for (int i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		for (int k = 2; k <= n; ++k)
		{
			for (int i = 0; i < n - k + 1; ++i)
			{
				int j = (k + i) - 1;
				if (k == 2 && text[i] == text[j])
				{
					// First similar pair
					dp[i][j] = 2;
				}
				else if (text[i] == text[j])
				{
					// Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i][j] = this->maxValue(dp[i][j - 1], 
                                              dp[i + 1][j]);
				}
			}
		}
		return dp[0][n - 1];
	}
};
int main()
{
	Subsequence *task = new Subsequence();
	string text1 = "pewmoozdp";
	string text2 = "xbfdsafx";
	string text3 = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	int ans = task->findLPS(text1);
	cout << "\n Given : " << text1;
	cout << "\n Result : " << ans;
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task->findLPS(text2);
	cout << "\n Given : " << text2;
	cout << "\n Result : " << ans;
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = task->findLPS(text3);
	cout << "\n Given : " << text3;
	cout << "\n Result : " << ans;
	return 0;
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
// Include namespace system
using System;
// Csharp program for
// Longest palindromic subsequence using dynamic programming
public class Subsequence
{
	// Returns the max value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int findLPS(String text)
	{
		int n = text.Length;
		if (n == 0)
		{
			return 0;
		}
		int[,] dp = new int[n,n];
		// Set 1 to all diagonal elements
		for (int i = 0; i < n; ++i)
		{
			dp[i,i] = 1;
		}
		for (int k = 2; k <= n; ++k)
		{
			for (int i = 0; i < n - k + 1; ++i)
			{
				int j = (k + i) - 1;
				if (k == 2 && text[i] == text[j])
				{
					// First similar pair
					dp[i,j] = 2;
				}
				else if (text[i] == text[j])
				{
					// Calculate sum the bottom left element + 2
					dp[i,j] = dp[i + 1,j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i,j] = this.maxValue(dp[i,j - 1], dp[i + 1,j]);
				}
			}
		}
		return dp[0,n - 1];
	}
	public static void Main(String[] args)
	{
		Subsequence task = new Subsequence();
		String text1 = "pewmoozdp";
		String text2 = "xbfdsafx";
		String text3 = "abbisstiwebaccess";
		// Test A
		// Text = pewmoozdp
		// "poop" is resultant palindrome
		// Length 4
		int ans = task.findLPS(text1);
		Console.Write("\n Given : " + text1);
		Console.Write("\n Result : " + ans);
		// Test B
		// Text = xbfdsafx
		// [xfsfx,xfdfx,xfafx] is resultant palindrome
		// Length 5
		ans = task.findLPS(text2);
		Console.Write("\n Given : " + text2);
		Console.Write("\n Result : " + ans);
		// Test C
		// Text = "abbisstiwebaccess"
		// [abissiba] is resultant palindrome
		// Length 8
		ans = task.findLPS(text3);
		Console.Write("\n Given : " + text3);
		Console.Write("\n Result : " + ans);
	}
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
package main
import "fmt"
// Go program for
// Longest palindromic subsequence using dynamic programming
type Subsequence struct {}
func getSubsequence() * Subsequence {
	var me *Subsequence = &Subsequence {}
	return me
}
// Returns the max value of given two numbers
func(this Subsequence) maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func(this Subsequence) findLPS(text string) int {
	var n int = len(text)
	if n == 0 {
		return 0
	}
	var dp = make([][] int, n)
	for i := 0; i < n; i++ {
		dp[i] = make([] int, n)
	}
	// Set 1 to all diagonal elements
	for i := 0 ; i < n ; i++ {
		dp[i][i] = 1
	}
	for k := 2 ; k <= n ; k++ {
		for i := 0 ; i < n - k + 1 ; i++ {
			var j int = (k + i) - 1
			if k == 2 && text[i] == text[j] {
				// First similar pair
				dp[i][j] = 2
			} else if text[i] == text[j] {
				// Calculate sum the bottom left element + 2
				dp[i][j] = dp[i + 1][j - 1] + 2
			} else {
				// When element are not same (i and j location)
				// Then change current element by max of 
				// left and down element
				dp[i][j] = this.maxValue(dp[i][j - 1], 
					dp[i + 1][j])
			}
		}
	}
	return dp[0][n - 1]
}
func main() {
	var task * Subsequence = getSubsequence()
	var text1 string = "pewmoozdp"
	var text2 string = "xbfdsafx"
	var text3 string = "abbisstiwebaccess"
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	var ans int = task.findLPS(text1)
	fmt.Print("\n Given : ", text1)
	fmt.Print("\n Result : ", ans)
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2)
	fmt.Print("\n Given : ", text2)
	fmt.Print("\n Result : ", ans)
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = task.findLPS(text3)
	fmt.Print("\n Given : ", text3)
	fmt.Print("\n Result : ", ans)
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
<?php
// Php program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
	// Returns the max value of given two numbers
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function findLPS($text)
	{
		$n = strlen($text);
		if ($n == 0)
		{
			return 0;
		}
		$dp = array_fill(0, $n, array_fill(0, $n, 0));
		// Set 1 to all diagonal elements
		for ($i = 0; $i < $n; ++$i)
		{
			$dp[$i][$i] = 1;
		}
		for ($k = 2; $k <= $n; ++$k)
		{
			for ($i = 0; $i < $n - $k + 1; ++$i)
			{
				$j = ($k + $i) - 1;
				if ($k == 2 && $text[$i] == $text[$j])
				{
					// First similar pair
					$dp[$i][$j] = 2;
				}
				else if ($text[$i] == $text[$j])
				{
					// Calculate sum the bottom left element + 2
					$dp[$i][$j] = $dp[$i + 1][$j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					$dp[$i][$j] = $this->maxValue($dp[$i][$j - 1], 
                                                  $dp[$i + 1][$j]);
				}
			}
		}
		return $dp[0][$n - 1];
	}
}

function main()
{
	$task = new Subsequence();
	$text1 = "pewmoozdp";
	$text2 = "xbfdsafx";
	$text3 = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	$ans = $task->findLPS($text1);
	echo("\n Given : ".$text1);
	echo("\n Result : ".$ans);
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	$ans = $task->findLPS($text2);
	echo("\n Given : ".$text2);
	echo("\n Result : ".$ans);
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	$ans = $task->findLPS($text3);
	echo("\n Given : ".$text3);
	echo("\n Result : ".$ans);
}
main();

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
// Node JS program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
	// Returns the max value of given two numbers
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	findLPS(text)
	{
		var n = text.length;
		if (n == 0)
		{
			return 0;
		}
		var dp = Array(n).fill(0).map(() => new Array(n).fill(0));
		// Set 1 to all diagonal elements
		for (var i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		for (var k = 2; k <= n; ++k)
		{
			for (var i = 0; i < n - k + 1; ++i)
			{
				var j = (k + i) - 1;
				if (k == 2 && text.charAt(i) == text.charAt(j))
				{
					// First similar pair
					dp[i][j] = 2;
				}
				else if (text.charAt(i) == text.charAt(j))
				{
					// Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i][j] = this.maxValue(dp[i][j - 1], dp[i + 1][j]);
				}
			}
		}
		return dp[0][n - 1];
	}
}

function main()
{
	var task = new Subsequence();
	var text1 = "pewmoozdp";
	var text2 = "xbfdsafx";
	var text3 = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	var ans = task.findLPS(text1);
	process.stdout.write("\n Given : " + text1);
	process.stdout.write("\n Result : " + ans);
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2);
	process.stdout.write("\n Given : " + text2);
	process.stdout.write("\n Result : " + ans);
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = task.findLPS(text3);
	process.stdout.write("\n Given : " + text3);
	process.stdout.write("\n Result : " + ans);
}
main();

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
#  Python 3 program for
#  Longest palindromic subsequence using dynamic programming
class Subsequence :
	#  Returns the max value of given two numbers
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def findLPS(self, text) :
		n = len(text)
		if (n == 0) :
			return 0
		
		dp = [[0] * (n) for _ in range(n) ]
		i = 0
		#  Set 1 to all diagonal elements
		while (i < n) :
			dp[i][i] = 1
			i += 1
		
		k = 2
		while (k <= n) :
			i = 0
			while (i < n - k + 1) :
				j = (k + i) - 1
				if (k == 2 and text[i] == text[j]) :
					#  First similar pair
					dp[i][j] = 2
				elif (text[i] == text[j]) :
					#  Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2
				else :
					#  When element are not same (i and j location)
					#  Then change current element by max of 
					#  left and down element
					dp[i][j] = self.maxValue(dp[i][j - 1], dp[i + 1][j])
				
				i += 1
			
			k += 1
		
		return dp[0][n - 1]
	

def main() :
	task = Subsequence()
	text1 = "pewmoozdp"
	text2 = "xbfdsafx"
	text3 = "abbisstiwebaccess"
	#  Test A
	#  Text = pewmoozdp
	#  "poop" is resultant palindrome
	#  Length 4
	ans = task.findLPS(text1)
	print("\n Given : ", text1, end = "")
	print("\n Result : ", ans, end = "")
	#  Test B
	#  Text = xbfdsafx
	#  [xfsfx,xfdfx,xfafx] is resultant palindrome
	#  Length 5
	ans = task.findLPS(text2)
	print("\n Given : ", text2, end = "")
	print("\n Result : ", ans, end = "")
	#  Test C
	#  Text = "abbisstiwebaccess"
	#  [abissiba] is resultant palindrome
	#  Length 8
	ans = task.findLPS(text3)
	print("\n Given : ", text3, end = "")
	print("\n Result : ", ans, end = "")

if __name__ == "__main__": main()

Output

 Given :  pewmoozdp
 Result :  4
 Given :  xbfdsafx
 Result :  5
 Given :  abbisstiwebaccess
 Result :  8
#  Ruby program for
#  Longest palindromic subsequence using dynamic programming
class Subsequence 
	#  Returns the max value of given two numbers
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def findLPS(text) 
		n = text.length
		if (n == 0) 
			return 0
		end

		dp = Array.new(n) {Array.new(n) {0}}
		i = 0
		#  Set 1 to all diagonal elements
		while (i < n) 
			dp[i][i] = 1
			i += 1
		end

		k = 2
		while (k <= n) 
			i = 0
			while (i < n - k + 1) 
				j = (k + i) - 1
				if (k == 2 && text[i] == text[j]) 
					#  First similar pair
					dp[i][j] = 2
				elsif (text[i] == text[j]) 
					#  Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2
				else
 
					#  When element are not same (i and j location)
					#  Then change current element by max of 
					#  left and down element
					dp[i][j] = self.maxValue(dp[i][j - 1], dp[i + 1][j])
				end

				i += 1
			end

			k += 1
		end

		return dp[0][n - 1]
	end

end

def main() 
	task = Subsequence.new()
	text1 = "pewmoozdp"
	text2 = "xbfdsafx"
	text3 = "abbisstiwebaccess"
	#  Test A
	#  Text = pewmoozdp
	#  "poop" is resultant palindrome
	#  Length 4
	ans = task.findLPS(text1)
	print("\n Given : ", text1)
	print("\n Result : ", ans)
	#  Test B
	#  Text = xbfdsafx
	#  [xfsfx,xfdfx,xfafx] is resultant palindrome
	#  Length 5
	ans = task.findLPS(text2)
	print("\n Given : ", text2)
	print("\n Result : ", ans)
	#  Test C
	#  Text = "abbisstiwebaccess"
	#  [abissiba] is resultant palindrome
	#  Length 8
	ans = task.findLPS(text3)
	print("\n Given : ", text3)
	print("\n Result : ", ans)
end

main()

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
import scala.collection.mutable._;
// Scala program for
// Longest palindromic subsequence using dynamic programming
class Subsequence()
{
	// Returns the max value of given two numbers
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def findLPS(text: String): Int = {
		var n: Int = text.length();
		if (n == 0)
		{
			return 0;
		}
		var dp: Array[Array[Int]] = Array.fill[Int](n, n)(0);
		var i: Int = 0;
		// Set 1 to all diagonal elements
		while (i < n)
		{
			dp(i)(i) = 1;
			i += 1;
		}
		var k: Int = 2;
		while (k <= n)
		{
			i = 0;
			while (i < n - k + 1)
			{
				var j: Int = (k + i) - 1;
				if (k == 2 && text.charAt(i) == text.charAt(j))
				{
					// First similar pair
					dp(i)(j) = 2;
				}
				else if (text.charAt(i) == text.charAt(j))
				{
					// Calculate sum the bottom left element + 2
					dp(i)(j) = dp(i + 1)(j - 1) + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp(i)(j) = maxValue(dp(i)(j - 1), dp(i + 1)(j));
				}
				i += 1;
			}
			k += 1;
		}
		return dp(0)(n - 1);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subsequence = new Subsequence();
		var text1: String = "pewmoozdp";
		var text2: String = "xbfdsafx";
		var text3: String = "abbisstiwebaccess";
		// Test A
		// Text = pewmoozdp
		// "poop" is resultant palindrome
		// Length 4
		var ans: Int = task.findLPS(text1);
		print("\n Given : " + text1);
		print("\n Result : " + ans);
		// Test B
		// Text = xbfdsafx
		// [xfsfx,xfdfx,xfafx] is resultant palindrome
		// Length 5
		ans = task.findLPS(text2);
		print("\n Given : " + text2);
		print("\n Result : " + ans);
		// Test C
		// Text = "abbisstiwebaccess"
		// [abissiba] is resultant palindrome
		// Length 8
		ans = task.findLPS(text3);
		print("\n Given : " + text3);
		print("\n Result : " + ans);
	}
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8
import Foundation;
// Swift 4 program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
	// Returns the max value of given two numbers
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func findLPS(_ data: String) -> Int
	{
      	var text = Array(data);
		let n: Int = text.count;
		if (n == 0)
		{
			return 0;
		}
		var dp: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: n), count: n);
		var i: Int = 0;
		// Set 1 to all diagonal elements
		while (i < n)
		{
			dp[i][i] = 1;
			i += 1;
		}
		var k: Int = 2;
		while (k <= n)
		{
			i = 0;
			while (i < n - k + 1)
			{
				let j: Int = (k + i) - 1;
				if (k == 2 && text[i] == text[j])
				{
					// First similar pair
					dp[i][j] = 2;
				}
				else if (text[i] == text[j])
				{
					// Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i][j] = self.maxValue(dp[i][j - 1], 
                                             dp[i + 1][j]);
				}
				i += 1;
			}
			k += 1;
		}
		return dp[0][n - 1];
	}
}
func main()
{
	let task: Subsequence = Subsequence();
	let text1: String = "pewmoozdp";
	let text2: String = "xbfdsafx";
	let text3: String = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	var ans: Int = task.findLPS(text1);
	print("\n Given : ", text1, terminator: "");
	print("\n Result : ", ans, terminator: "");
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2);
	print("\n Given : ", text2, terminator: "");
	print("\n Result : ", ans, terminator: "");
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = task.findLPS(text3);
	print("\n Given : ", text3, terminator: "");
	print("\n Result : ", ans, terminator: "");
}
main();

Output

 Given :  pewmoozdp
 Result :  4
 Given :  xbfdsafx
 Result :  5
 Given :  abbisstiwebaccess
 Result :  8
// Kotlin program for
// Longest palindromic subsequence using dynamic programming
class Subsequence
{
	// Returns the max value of given two numbers
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun findLPS(text: String): Int
	{
		val n: Int = text.length;
		if (n == 0)
		{
			return 0;
		}
		val dp: Array < Array < Int >> = Array(n)
		{
			Array(n)
			{
				0
			}
		};
		var i: Int = 0;
		// Set 1 to all diagonal elements
		while (i < n)
		{
			dp[i][i] = 1;
			i += 1;
		}
		var k: Int = 2;
		while (k <= n)
		{
			i = 0;
			while (i < n - k + 1)
			{
				val j: Int = (k + i) - 1;
				if (k == 2 && text.get(i) == text.get(j))
				{
					// First similar pair
					dp[i][j] = 2;
				}
				else if (text.get(i) == text.get(j))
				{
					// Calculate sum the bottom left element + 2
					dp[i][j] = dp[i + 1][j - 1] + 2;
				}
				else
				{
					// When element are not same (i and j location)
					// Then change current element by max of 
					// left and down element
					dp[i][j] = this.maxValue(dp[i][j - 1], dp[i + 1][j]);
				}
				i += 1;
			}
			k += 1;
		}
		return dp[0][n - 1];
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subsequence = Subsequence();
	val text1: String = "pewmoozdp";
	val text2: String = "xbfdsafx";
	val text3: String = "abbisstiwebaccess";
	// Test A
	// Text = pewmoozdp
	// "poop" is resultant palindrome
	// Length 4
	var ans: Int = task.findLPS(text1);
	print("\n Given : " + text1);
	print("\n Result : " + ans);
	// Test B
	// Text = xbfdsafx
	// [xfsfx,xfdfx,xfafx] is resultant palindrome
	// Length 5
	ans = task.findLPS(text2);
	print("\n Given : " + text2);
	print("\n Result : " + ans);
	// Test C
	// Text = "abbisstiwebaccess"
	// [abissiba] is resultant palindrome
	// Length 8
	ans = task.findLPS(text3);
	print("\n Given : " + text3);
	print("\n Result : " + ans);
}

Output

 Given : pewmoozdp
 Result : 4
 Given : xbfdsafx
 Result : 5
 Given : abbisstiwebaccess
 Result : 8


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved