AcWing 1017. 怪盗基德的滑翔翼 java版本
原题链接
简单
作者:
JAVA小老弟
,
2020-02-04 22:45:06
,
所有人可见
,
阅读 907
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader r=new BufferedReader(new InputStreamReader(System.in));
String s[]=r.readLine().split(" ");
int n=Integer.parseInt(s[0]);
for (int i = 0; i <n ; i++) {
String line1[]=r.readLine().split(" ");
String line2[]=r.readLine().split(" ");
int num=Integer.parseInt(line1[0]);
int[] arr=new int[num];
//将所有楼的高度存入arr中
for (int j = 0; j <num; j++) {
arr[j]=Integer.parseInt(line2[j]);
}
//定义一个left数组 从右到左遍历的结果
//定义一个 right数组 从左到右遍历的结果
int[] left=new int[num];
int[] right=new int[num];
int res=0;
//赋值 初始化最少为1
Arrays.fill(left,1);
Arrays.fill(right,1);
//两层for 存在低的楼就有可能成为更新的目标
for (int j = 1; j <num ; j++) {
for (int k = j-1; k>=0 ; k--) {
if(arr[k]<arr[j])
{
right[j]=Math.max(right[k]+1,right[j]);
res=Math.max(right[j],res);
}
}
}
for (int j = num-2; j >=0 ; j--) {
for (int k = j+1; k<num ; k++) {
if(arr[k]<arr[j])
{
left[j]=Math.max(left[k]+1,left[j]);
res=Math.max(left[j],res);
}
}
}
//最后输出结果
System.out.println(res);
}
}
}