最长公共子序列的常用代码如下
public class Solution {
/*给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。
说明
最长公共子序列的定义：
最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。
该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。
样例
给出"ABCD" 和 "EDCA"，这个LCS是 "A" (或 D或C)，返回1
给出 "ABCD" 和 "EACB"，这个LCS是"AC"返回 2
* @param A: A string
* @param B: A string
* @return: The length of longest common subsequence of A and B
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
int m= A.length()+1;
int n= B.length()+1;
int[][] dp = new int[m][n];
dp[0][0] = A.charAt(0)==B.charAt(0) ? 1 : 0;//dp矩阵的首个字符是否相等
for (int i =1; i++; i<m) {
dp[i][0]=Math.max(dp[i-1][0],A.charAt(i-1)==B.charAt(0) ? 1 : 0);
}//dp矩阵初始化第一列
for (int j=0; j++; j<n) {
dp[0][j]=Math.max(dp[0][j-1],A.charAt(0)==B.charAt(j-1) ? 1 : 0);
}//dp矩阵初始化第一行
for (int i=1; i++; i<m) {
for (int j=1; j++; j<n) {
dp[i][j]= Math.max(dp[i][j-1],dp[i-1][j]);//不想等的情况下
if (A.charAt(i-1)==B.charAt(j-1)) {
dp[i][j]=Math.max(dp[i][j],dp[i-1]//当前字符相等的情况下看的比较[j-1]+1);
}
}
}
return dp[m][n];
}
}`
最长公共子数组的常用代码
`
public class Solution {
/*
给出两个字符串，找到最长公共子串，并返回其长度。
注意事项
子串的字符应该连续的出现在原字符串中，这与子序列有所不同。
样例
给出A=“ABCD”，B=“CBCE”，返回 2
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code her
if (A.length()==0||B.length()==0) {
return 0;
}
if (A.length()==1||B.length()==1) {
return 1;
}
int m = A.length();
int n = B.length();
int max= 0;
int[][] dp = new int[m][n];
for (int i=0; i<m; i++) {
if (A.charAt(i)==B.charAt(0)) {
dp[i][0] = 1;
}
}
for (int j=0; i<n; i++) {
if (A.charAt(0)==B.charAt(j)) {
dp[0][j] = 1;
}
}
for (int i=1; i<m; i++) {
for (int j=1; j<n; j++) {
if (A.charAt(i)==B.charAt(j)) {
max=Math.max(dp[i][j]=dp[i-1][j-1]+1,max);
}
}
}
return max;
}
public class Solution {
/*
最长上升连续子序列
给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。
（最长上升连续子序列可以定义为从右到左或从左到右的序列。）
样例
给定 [5, 4, 2, 1, 3], 其最长上升连续子序列（LICS）为 [5, 4, 2, 1], 返回 4.
给定 [5, 1, 2, 3, 4], 其最长上升连续子序列（LICS）为 [1, 2, 3, 4], 返回 4.
*/
*@param A : An array of Integer
* @return : an integer
*/
public int longestIncreasingContinuousSubsequence(int[] A) {
int[] dp= new int[A.length];
int[] dp2 = new int[A.length];
int maxLen= 0;
int maxLen2= 0;
for (int i=0; i<dp.length; i++) {
dp[i]=1;
dp2[i]=1;
for (int j=0; j<i; j++ ) {
if (A[i]>A[j]) {
dp[i]= Math.max(dp[i],dp[j]+1);
}
}
for (int j=0; j<i; j++) {
if (A[i]<A[j]) {
dp2[i]=Math.max(dp2[i],dp2[j]+1)
}
}
if (dp2[i]>maxLen2) {
maxLen2=dp2[i];
}
if (dp[i]>maxLen) {
maxLen=dp[i];
}
}
return maxLen>maxLen2 ? maxLen : maxLen2;
}
}