最长回文子串-最长公共子序列

最长回文子串-最长公共子序列"/>

最长回文子串-最长公共子序列

package arithmetic.dynamicplan;import java.util.Arrays;public class Demo01 {/*** 最长回文串* L[i,j]表示X[i~j]的最长回文串长度* L[i,j] = {*     1                         i=j*     L[i+1,j-1]+2             And{i<j,X[i]=X[j],L[i+1][j-1]=j-i-1}*     Max{L[i,j-1],L[i+1,j]}   And{i<j,Or{X[i]!=X[j],L[i+1][j-1]!=j-i-1}}* }* @param args*/public static void main(String[] args) {String A = "aacd";System.out.println(getLongestPalindrome(A, A.length()));}public static int getLongestPalindrome(String A, int n) {// write code hereint[][] L = new int[n][n];for(int i = 0; i < n; ++i){L[i][i] = 1;}int i, j = 1;while (j < n){i = j - 1;while(i >= 0){//  中间是连续回文，且ij元素相同if(A.charAt(i) == A.charAt(j) && L[i + 1][j - 1] == j - i - 1){L[j][i] = L[i][j] = L[i + 1][j - 1] + 2;//  中间不是连续回文，无论ij元素是否相同}else{L[j][i] = L[i][j] = Math.max(L[i][j - 1],L[i + 1][j]);}--i;}++j;}for(i = 0; i < n; i++){System.out.println(Arrays.toString(L[i]));}return L[0][n-1];}}

package arithmetic.dynamicplan;import java.util.Arrays;public class Demo02 {/*** 最长公共子序列* L[i,j]表示X[1~i]与Y[1~j]的最长公共子序列长度* L[i,j] = {*     0                        i=0,j=0*     L[i-1,j-1]+1             And{i>0,j>0,X[i]=Y[i]}*     Max{L[i,j-1],L[i-1,j]}   And{i>0,j>0,X[i]!=Y[i]}* }* @param args*/public static void main(String[] args) {int[] arr1 = {2,1,3,5,6,7,2};int[] arr2 = {3,9,5,2,6,5};System.out.println(getLongestSubsequence(arr1, arr2));}public static int getLongestSubsequence(int[] arr1,int[] arr2) {int[][] L = new int[arr1.length + 1][arr2.length + 1];for(int i = 1; i <= arr1.length; ++i){for(int j = 1; j <= arr2.length; ++j){if(arr1[i - 1] == arr2[j - 1]){L[i][j] = L[i - 1][j - 1] + 1;}else{L[i][j] = Math.max(L[i][j - 1], L[i - 1][j]);}}}for(int i = 0; i <= arr1.length; i++){System.out.println(Arrays.toString(L[i]));}return L[arr1.length][arr2.length];}
}