【算法】最长上升子序列(LIS)
算法描述
给定一个长度为n的字符串r,求字符单调递增的子序列的长度最长为多少
大致步骤
1.创建一个记录到达对应位置的上升子序列个数的dp数组
2.若字符串只有1个元素,元素本身就构成了最长上升子序列,因此全部元素初始化1
3.用两层for循环比较,第一层从第2个元素开始,逐个记录出dp数组的元素的值
4.第二层用将小于i的前面所有数组元素都进行比较大小
5.判断若为递增,则将记录到达i元素时,已经累计多少个上升子序列个数赋值给dp数组
6.最后创建一个变量并返回最大的dp数组值
代码实现
//时间复杂度O(n^2)
import java.util.Arrays;
import java.util.Scanner;
public class LIS{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] r = new int[n];
for(int i=0; i<n; i++) {
r[i] = sc.nextInt();
}
System.out.println(LIS(r));
}
/*dp[j]+1指的是比较的j位置已经记录之前到达它的上升子序列的个数再加上第i个这一个元素*/
static int LIS(int[] r) {
if(r.length==0) return 0;
int[] dp = new int[r.length]; //记录
Arrays.fill(dp, 1); //全部元素初始化为1
int res = dp[0];
for(int i=1; i<r.length; i++) {
for(int j=0; j<i; j++) {
if(r[i]>r[j]) {
dp[i] = Math.max(dp[i], dp[j]+1); //状态转移
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
运行结果
//输入数据
7
1 7 3 5 9 4 8
4