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