先来看问题，
最长递增子列。
即数组中按顺序拿出n个数，（按照原来的顺序）该子数列为递增数列。
例如：1 2 3 -1数列最后结果为3.最对应数列很显然为1 2 3
（注，只输出长度。）
当然如果还需要对应坐标对算法进行稍加改动即可
这里主要是对思路进行理解
废话少说 下面我们开始讲解大致思路 （动态规划）
我们对数组的前n个数即第一个，第二个 第n个 分别求出以第一个，第二个， 第n好个结尾的最长连续递增子序列 那么，当我们输入第n+1个数时我们只需往前比较，找到比第n+1位小的数 ，记做第X位 ，由于我们已经得到以第X位为结尾的最长连续递增子序列的长度（记做Y） 所以 我们的以n+1位位结尾的最长连续递增子序列即为Y+1
我们依次向前对比 记录比n+1为小的 并且对应长度的最最大值 加一即可
所以我们从第一位往后知道遍历结束 就可以得出以每一位为结尾的最长连续递增子序列的长度。 故我们就可以得出结果
当然你也可以得出对应序列 这里对得出序列的步骤就不具体讲了
下面 我们看具体代码
package abc;
import java.util.Map;
import java.util.Scanner;
public class zcdzzxl {
//最长递增子序列
public static int gerLong(int[] a){//返回最长递增子列的长度
if (a==null || a.length==0){
return 0;
}//特殊情况
//求长度方法
int Max=1;
int max;
int i,j;
int[] n=new int[a.length];
n[0]=1;
for (i=1;i){
max=0;
for (j=i-1;j>=0;j--){
if (a[i]>a[j]){
if (n[j]>max){
max=n[j];
}
}
}
n[i]=max+1;
if (n[i]>Max){
Max=n[i];
}
}
putArray(a,n,Max);
//此处调用输出函数
return Max;//返回长度
}
public static void putArray(int[] Array,int[] array ,int longest){
int i,j=0;
int max;
for (i=array.length-1;i>=0;i--){
if (array[i]==longest){
j=i;
break;
}
}//寻找递增子列的最后一个数的下标
int[] to=new int[longest];//存储子列
to[--longest]=Array[j];
for (i=j-1;i>=0;i--){
if (Array[i]longest){
to[--longest]=Array[i];
}
}
System.out.println("子列为: ");
for (i=0;i){
System.out.print(to[i]+" ");
}//当然 对于同一个数组，对应的子列 也可能不唯一
}
public static void main(String [] args){
Scanner in=new Scanner(System.in);
System.out.println("输入测试数组长度");
int n=in.nextInt();
System.out.println("请依次输入数组内容");
int[] test=new int[n];
for (int i=0;i){
test[i]=in.nextInt();
}
System.out.println("测试得到的最长递增子列长度为"+gerLong(test));
}
}
这是测试输出结果图
这里也写了输出具体序列的代码 可以自己研究一下
如果有什么不对的地方 或者不太看的懂的地方 评论区留言
谢 ！！
Original: https://www.cnblogs.com/cndccm/p/12207796.html
Author: Mr小明同学
Title: （动态规划）最长递增子列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/573028/
转载文章受原作者版权保护。转载请注明原作者出处！