方法一：
思想
由大到小的截取并返回 保证如果返回肯定是返回最大的
短字符串的处方式:第一次for循环:递减 。第二次for循环 ：截取该长度字符串的可行方案个数 然后截取
长字符串长度处理方案:截取"第一次截取的字符串" 可行方案个数 两次截取内容一致，返回
1、获得最长公共子序列--可以 返回 “最长公共子序列的长度” 或者 “最长公共子序列”
public static int getmaxsubstr(String str1, String str2){int length1=str1.length();int length2=str2.length();String bigstr= length1>length2?str1:str2;//bigstr保存最长String smallstr=length1<=length2?str1:str2;//small保存最短for(int i=smallstr.length();i>=1;i--)//短的处理:从最后往前刷， n n-1...1i=smallstr.length 要循环走一遍{for(int j=0;j<=smallstr.length()-i;j++) //8 例如当i为n-1有两种截取方式{// System.out.println(j+" "+i);String substring=smallstr.substring(j,j+i);//交错取出子串 每次截取i个长度for(int k=0; k<=bigstr.length()-i;k++)//减去长度 9 长的处理：截取时循环次数{//equals也行if(bigstr.substring(k,k+i).endsWith(substring)) //保证截取的长度为i，并每次指针前移{System.out.println(substring);//最长公共子序列return i;//返回 相似度的长度}}}}
写了一个注释
public static int getmaxsubstr( String str1, String str2){int length1=str1.length();int length2=str2.length();String bigstr= length1>length2?str1:str2;//标记区分长的字符串和短的字符串String smallstr=length1<=length2?str1:str2;// 指针：获得所有子字符串长度的指针// 例如 字符串长度为10 获得长度为10 9 8 7 6 5 4 3 2 1的字符串for(int i=smallstr.length();i>=1;i--)//短的处理:从最后往前刷， n n-1...1i=smallstr.length 要循环走一遍{//字符串长度为10 截取长度为10的只有一种可能 str(0,9)//字符串长度为10 截取长度为9 有2中可能 str(0,9) str(1,10)//字符串长度为10 截取长度为9 以此类推//故j的下标从0开始，要截取i个数据，故指针对多滑动到str.length-i for(int j=0;j<=smallstr.length()-i;j++) {String substring=smallstr.substring(j,j+i);// 重点： 求字符串所有公共子串for(int k=0; k<=bigstr.length()-i;k++)//对长字符串处理方式同短字符串{//equals也行if(bigstr.substring(k,k+i).endsWith(substring)) //截取的字符串长度仍然是 i{System.out.println(substring);//重点： 最长公共子序列return i;//返回 相似度的长度 即截取字符串的长度 }}}}
2、自定义相似度
public static double getSimilarDegree(String str1, String str2){int num=getmaxsubstr( str1, str2);//返回 “最长公共子序列的长度” 或者 “最长公共子序列” System.out.println(num);double s1=num*1.0/str1.length();double s2=num*1.0/str2.length();return (s1+s2)/2;}
3、测试
public static void main(String[] args) {String str1="12344567"; //112344567 235545679 String str2="235545679";//0.6double result=getSimilarDegree( str1, str2);if( result>0.5){System.out.println("相似度很高"+result);}else{System.out.println("相似度很低"+result);}}
方法二求最长递增子序列
使用回溯法
最长递增序列不要求数组元素连续问题，返回递增序列长度和递增序列。o(n^2)做法，顺序比较以第i个元素开头的递增序列即可。
利用动态规划来做，假设数组为1, -1, 2, -3, 4, -5, 6, -7。我们定义LIS[N]数组，其中LIS[i]用来表示以array[i]为最后一个元素的最长递增子序列。
使用i来表示当前遍历的位置：
当i = 0 时，显然，最长的递增序列为（1），则序列长度为1。则LIS[0] = 1
当i = 1 时，由于-1 < 1，因此，必须丢弃第一个值，然后重新建立序列。当前的递增子序列为（-1），长度为1。则LIS[1] = 1
当i = 2 时，由于2 > 1，2 > -1。因此，最长的递增子序列为(1, 2)，(-1, 2)，长度为2。则LIS[2] = 2。
当i = 3 时，由于-3 < 1, -1, 2。因此，必须丢掉前面的元素，重建建立序列。当前的递增子序列为（-3），长度为1。则LIS[3] = 1。
依次类推之后，可以得出如下结论。
LIS[i] = max{1, LIS[k] + 1}, array[i] >array[k], for any k < i
最后，我们取max{Lis[i]}。
public static void getLongestAscSequence(int []input,int size){int []arr = new int[size];// 用来存储以第i个元素结尾的最长递增子序列int maxLen = 1;for (int i = 0; i < size; i++){arr[i] = 1 ;for ( int j = 0; j < i; j++){if ((input[i] > input[j]) && (arr[j] +1 > arr[i]) )arr[i] = arr[j] + 1;}if (maxLen < arr[i]){maxLen = arr[i];}}System.out.println(maxLen);}
附：最大子数组之积
题目描述： 给定一个长度为N的整数数组，只允许用乘法，计算任意（N-1）个数的组合中乘积最大的一组。算法分析： 动态规划的做法，假设数组为a[N]，max[N]表示以下标为i结尾的子数组乘积最大值，min[N]表示以下标为i结尾的子数组乘积最小值。为了处理数组元素为负的问题，必须将最小乘积也保存起来。 很容易想到，若当前元素a[i]为负数，那么a[i]*max[i-1]得到的值并不一定比a[i] *min[i-1]大，因为min[i-1]可能为负，如果min[i-1]的绝对值大于max[i-1]，那么a[i] *min[i-1]负负相乘的值则更大。因此有以下转移方程 求三者最大 max[i] = MaxinThree(a[i], a[i]*max[i-1],a[i]*min[i-1])求三者最小 min[i] = MininThree(a[i], a[i]*max[i-1], a[i]*min[i-1])
//a b 最大值与c比较 三者谁大取哪一个值static int MaxinThree(int a, int b, int c) {return (((a > b) ? a : b) > c) ? (a > b ? a : b) : c;}static int MinThree(int a, int b, int c) {return (((a < b) ? a : b) < c) ? (a < b ? a : b) : c;}static void getBiggestMultiOfSubArray(int input[],int size) {List ls=new ArrayList<>();int max[]=new int[size];int min[]=new int[size];int product;max[0]=min[0]=input[0];product=max[0];for (int i=1;i<size;i++ ) {//比较当前值、当前值与之前所有乘积最大值、当前值与之前所有乘积最小值 三者之间 的最大值max[i]=MaxinThree(input[i], input[i]*max[i-1], input[i]*min[i-1]);min[i]=MinThree(input[i], input[i]*min[i-1], input[i]*max[i-1]);if(max[i]>product) {ls.add(max[i]);product=max[i];}}System.out.println(product);System.out.println(ls);}public static void main(String[] args) {int input[]= {5,-1,-2,4,9,1};getBiggestMultiOfSubArray(input,6);}
如果想要得到字符串序列：其实x>0可以加入list；当x<0时，当有偶数个负数也可以加入list。
