AcWing 1014. 登山
原题链接
简单
作者:
季之秋
,
2021-04-11 14:22:27
,
所有人可见
,
阅读 148
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int N = 1010;
int up[] = new int[N]; // 以n结束
int down[] = new int[N]; // 以n开头
int a[] = new int[N];
for(int i = 1; i <= n ; i ++) a[i] = sc.nextInt();
for(int i = 1; i <= n ; i ++){ // 正序求以i为结尾的单调序列长度
up[i] = 1;
for(int j = 1; j < i ; j ++){ // 第二层循环顺序无关紧要 因为在此之前每一个f[j] 都被确定了值,
// 所以与遍历顺序无关,切记是用更新过的值去更新现在的值
if(a[i] > a[j]) up[i] = Math.max(up[i], up[j] + 1);
}
}
for(int i = n; i >= 1; i --){ // 逆序求以i为开头的单调序列长度
down[i] = 1;
for(int j = i + 1; j <= n ; j ++){
if(a[i] > a[j]) down[i] = Math.max(down[i], down[j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n ; i ++) res = Math.max(res, up[i] + down[i] - 1); // 第i个点重合了
System.out.println(res);
}
}