LCS 解决两个字符串中最长公共子字符串的问题 java实现

问题如下 ：

     给定两个由整数组成的字符串，定义公共字符串为在两个字符串中取得两个任意N项，这N项在两个字符串中顺序相同，但是这N项不必在字符串中连续，只需要顺序相同即可，要你设计一个程序，输入两个字符串，输出最大子字符串的元素数量

    解析：可以这么考虑，设两个字符串为datas1（n项）,datas2（m项）,设置一个二维数组n*m的max保存在当datas1取第i项，datas2中取第j项，之前的最大子列元素数目，那么假如datas1中第i项和datas2中第j项相同，那么max[i][j] = max[i-1][j-1]+1;(注意，为了写代码方便，在写代码时候我故意将max数组多设置一行一列，设置为在max中0代表不取任何元素，1代表取第1个元素)如果这两项不一样，那么取max[i][j] = max(max[i][j-1],max[i-1][j]，这样将所有情况遍历之后，max[n-1][m-1]就是最大子列的元素数目，所以代码如下 ：

import java.util.*;
public class LCStest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] datas1 = new int[n];
    int m = sc.nextInt();
    int[] datas2 = new int[m];
    int[][] max = new int[n+1][m+1];
    for(int i=0;i<n;i++){
    	datas1[i] = sc.nextInt();
    }
    for(int i=0;i<m;i++){
    	datas2[i] = sc.nextInt();
    }
    for(int i=0;i<n;i++){
    	for(int j=0;j<m;j++){ 
    			  if(datas1[i] == datas2[j]){
    	  				max[i+1][j+1] = max[i][j]+1;
    	  			  }else{
    	  				max[i+1][j+1] = max(max[i][j+1],max[i+1][j]);
    	  		      }
    	}
    }
    System.out.print(max[n][m]);
	}
	
	public static int max(int a,int b){
		if(a>b){
			return a;
		}else{
			return b;
		}
	}

}

结果如下 ：