您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【算法】最长上升子序列(LIS)

【算法】最长上升子序列(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

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进