1014. 登山

• ①. 题目
• ②. 思路
• ③. 学习点
• ④. 代码实现

原题链接

①. 题目

②. 思路

• 还是一样，正反预处理一遍每一个点的最长上升子序列，最后再枚举一下每个点正反最长子序列和的最大值，记得-1，枚举的点是重复记录了一次
• 预处理出以每个点结尾的正向的最长上升子序列的值f[i]，以每个点结尾的反向的最长上升子序列的值g[i]
• res = max(f[i] + g[i] - 1),i = 1,2,3…n

③. 学习点

最长上升子序列

④. 代码实现

import java.util.Scanner;

public class _1014_登山_最长上升子序列进阶版 {
	static int N=1010;
	static int[] a=new int[N];
	static int[] f=new int[N];
	static int[] g=new int[N];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i =1; i <=n; i++) {
			a[i]=sc.nextInt();
		}
		
		//正向LIS
		for (int i =1; i <=n; i++) {
			f[i]=1;
			for (int j = 1; j <i; j++) {
				if(a[j]<a[i]) f[i]=Math.max(f[i], f[j]+1);
			}
		}
		
		//反向LIS
		for (int i =n; i>=1; i--) {
			g[i]=1;
			for (int j =n; j>i; j--) {
				if(a[j]<a[i]) g[i]=Math.max(g[i], g[j]+1);
			}				
		}

		//枚举每一个点,计算最大值
		int res=0;
		for (int i =1; i <=n; i++) {
			res=Math.max(res, f[i]+g[i]-1);
		}
		System.out.println(res);
	}
}