# 1. Introduction

The Longest Palindromic Subsequence (LPS) is a classic computational problem. Given a sequence, the challenge is to find the length of the longest subsequence that can also be read the same way in reverse order. Dynamic Programming offers an efficient solution to the LPS problem by breaking it down into smaller subproblems.

# 2. Program Steps

1. Create a function *lps* that takes in a string as its parameter.

2. Initiate a 2D array *dp* to store lengths of longest palindromic subsequences of substrings.

3. Using nested loops, fill in the table with the lengths of the longest palindromic subsequences.

4. The value in the top-right cell *dp[0][n-1]* is the solution to the problem.

5. Within the *main* method, use a sample string and display its longest palindromic subsequence length.

# 3. Code Program

```
class LongestPalindromicSubsequence {
public static int lps(String str) {
int n = str.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
for (int cl = 2; cl <= n; cl++) {
for (int i = 0; i < n - cl + 1; i++) {
int j = i + cl - 1;
if (str.charAt(i) == str.charAt(j) && cl == 2) {
dp[i][j] = 2;
} else if (str.charAt(i) == str.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
}
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
String str = "MAGNETIC";
System.out.println("The length of the LPS for " + str + " is: " + lps(str));
}
}
```

### Output:

The length of the LPS for MAGNETIC is: 3

# 4. Step By Step Explanation

1. The function *lps* determines the length of the longest palindromic subsequence in a given string.

2. For each possible substring, we use the dynamic programming approach to calculate its LPS length.

3. If the characters at the start and end of a substring are the same, the length is derived from the sub-string in-between them plus two.

4. Otherwise, it's the maximum of the lengths of the two substrings produced by removing either the start or end character.

5. In the *main* function, for the string "MAGNETIC", the longest palindromic subsequence is "ANA", which has a length of 3.