最长公共子序列：
字符串a："android"。
字符串b："random"。
最长公共子序列为：ando
最长连续公共子序列为：and，因为o和and之间隔开了。
思想：使用动态规划法，用一个二维数组，i 行表示当前选中s1的前 i 字符，列 j 表示当前选中s2的前 j 个字符，dp[i][j]表示当前i和j情况下最大子序列有多少个。（连续子序列使用max来保存最大）。
动态规划递推公式：
a.charAt（ i ）== b.chaiAt（ j ）时，dp[i][j] = dp [i-1][j-1] + 1;
其他时候，dp[i][j] = max（dp[i-1][j] , dp[i][j-1]）;
代码如下：
package 动态规划;public class LCS {//最长公共子序列public static void findLCS(String a ,String b) {int s1len = a.length();int s2len = b.length();char[] s1 = a.toCharArray();char[] s2 = b.toCharArray();int[][] lcs = new int[s1len][s2len];//把第一行写好int flag = 0;for (int i = 0; i < s2len ; i++) {if (s1[0] == s2[i]) {flag = 1;}lcs[0][i] = flag;}//吧第一列写好flag = 0;for (int i = 0; i < s1len; i++) {if (s2[0] == s1[i]) {flag = 1;}lcs[i][0] = flag;}for (int i = 1; i < s1len; i++) {for (int j = 1; j < s2len; j++) {if (s1[i] == s2[j]) {//如果对比时，某两个字符相等，那么当前最大值 = 两个s都不看这个当前字符时候的最大值+1lcs[i][j] = lcs[i - 1][j - 1] + 1;}else {//他等于两个字符串分别上一次匹配的最大值lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);}}}// displayArr(lcs ,s1len , s2len);System.out.println(lcs[s1len - 1][s2len - 1]);}//最长连续公共子序列public static void findContinueLCS(String a,String b) {int len1 = a.length();int len2 = b.length();int dp[][] = new int[len1+1][len2+1];for (int i = 0; i < dp.length; i++) {dp[i][0] = 0;}for (int i = 0; i < dp[0].length; i++) {dp[0][i] = 0;}int max = 0;for (int i = 1; i < dp.length; i++) {for (int j = 1; j < dp[0].length; j++) {if (a.charAt(i-1) == b.charAt(j-1)) {if (i == 0|| j == 0) {dp[i][j] = 1;}else {dp[i][j] = dp[i-1][j-1] + 1;}}else {dp[i][j] = 0;}if (max < dp[i][j]) {max = dp[i][j];}}}System.out.println(max);}//打印数组public static void displayArr(int[][] arr, int row, int col) {for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {System.out.print(arr[i][j] + " ");}System.out.println();}}public static void main(String[] args) {// TODO 自动生成的方法存根String a = "android";String b = "random";findLCS(a, b);findContinueLCS(a, b);}}
