此题目和上面的方格取数基本是一样的。
此题目描述是：从左上角传到右下角和从右下角传到左上角各一次，但是此是一个点不能重复走两次（和上面的方格取数的走完会清零不同），首先，我们可以转换为都是从左上角开始向右下角同时开始，此时和方格取数差不多了）
🌈重点需要理解的是：
方格取数是可以两次重复走到一个地方，但是最优解肯定不会走相同的地方。
本题是不可以走相同的地方。
经过转换后，所以两道题的代码基本是一样的。
下面的证明是从大佬的题解看到的大佬题解

对于没有交点的情况，我们不需要考虑。 主要是证明为什么不会取到走到同一点的情况。

比如上方红色是A路线，绿色是B路线。 存在相交的地方，我们只需要交换路线即可，对答案并没有任何影响。
用橙色代表与绿色交换后的红色，用亮绿色代表与红色交换后的绿色，可以得到如下路线：

但是很明显可以看到还是有同时走到的点，但是由于
这个条件，我们可以知道绕路走的
话肯定是比走同一个点更优。我们可以寻找绿色绕路或者蓝色绕路的最优值。

很明显就是最长上升子序列，它可以选择从最高楼层的顶部开始进行下落。但是题目中说了它可以从任何一个楼开始，但是开始后就不能改变方向，所以有两种情况：
（1）从左到右，最高的在右边，然后我们需要求的就是最长上升子序列（对应于样例中的2、3）需要求最长上升子序列
（2）从右往左飞，最高的在左边，我们需要求得就是最长下降子序列，但是本质都是一样的，进行两次即可。

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 110;static int[] h = new int[N];static int[] dp = new int[N]; //最长上升子序列static int[] dp2 = new int[N]; //最长下降子序列static int k = 0, n = 0;public static void main(String[] args) throws Exception{k = Integer.parseInt(br.readLine());while(k-- > 0) {n = Integer.parseInt(br.readLine());String[] hh = br.readLine().split(" ");for(int i = 1; i <= n; i++) {h[i] = Integer.parseInt(hh[i - 1]);}for(int i = 1; i <= n; i++) {dp[i] = 1;for(int j = 1; j < i; j++) {if(h[j] < h[i]) {dp[i] = Math.max(dp[i],dp[j] + 1); }}}int ans = 0;for(int i = 1; i <= n; i++) {ans = Math.max(dp[i],ans);}for(int i = 1; i <= n; i++) {dp2[i] = 1;for(int j = 1; j < i; j++) {if(h[j] > h[i]) {dp2[i] = Math.max(dp2[i],dp2[j] + 1); }}}for(int i = 1; i <= n; i++) {ans = Math.max(dp2[i],ans);}System.out.println(ans);}}
}

对于第一种情况：就是求最长上升子序列；
第二种情况：就是求最长下降子序列；
第三种情况：就是求最长上升子序列和最长下降子序列的最大值。
综上，我们只需要求解最长上升子序列和最长下降子序列的最大值。

第一次看题觉得和上面的差不多，但是需要注意，此题是可以下山，就是下山的过程中也是可以看的，我们需要求得是两者的和，
但是我们需要注意的是，up和down是有区别的，和上一题不同，因为我们求最长上升子序列的时候，求得是以i为结尾的最长上升子序列，那么如果我们对于down和up都这样求得话肯定是不行的，我们需要稍微改变一下down[]的定义：

up[i]：以i为结尾的最长上升子序列
down[i]:以i为开头的最长下降子序列。

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = 1100;static int[] h = new int[N];static int[] up = new int[N]; //最长上升子序列static int[] down = new int[N];static int k = 0, n = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[] hh = br.readLine().split(" ");for(int i = 1; i <= n; i++) {h[i] = Integer.parseInt(hh[i - 1]);}for(int i = 1; i <= n; i++) {up[i] = 1;for(int j = 1; j < i; j++) {if(h[j] < h[i]) {up[i] = Math.max(up[i],up[j] + 1); }}}//down[i]代表以i为左端点的最长下降子序列	for(int i = n; i >= 1; i--) {down[i] = 1;for(int j = n; j > i; j--) {if(h[i] > h[j]) {down[i] = Math.max(down[i],down[j] + 1);}}}int ans = 0;for(int i = 1; i <= n; i++) {ans = Math.max(ans,up[i] + down[i] - 1);
//				System.out.println(i + " " + up[i] + " " + down[i] + " " + ans);}System.out.println(ans);}
}

这题需要通过画图去转换，否则很难直接看出来：

很明显红色的是不可以的，绿色这种建桥方式是可行的。 我们可以看到只要两岸的城市都保证是上升子序列即可。 但是他们之间存在各自的一对一关系，起初想着分别求LIS，然后求两者最小值的最大值，这种方法是不可行的，主要是我们需要保证他们之间的对应关系。
那么我们可以通过一边对这对对应关系进行排序，然后再对另一边求最长上升子序列即为答案。
画图理解比较直观一点：

上面的两种情况都是可以的，所以最终答案就为4

题目理解完毕，开始写代码（主要就是LIS）

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (2e5 + 10);static node[] info = new node[N];static int[] dp = new int[N]; //最长上升子序列static int k = 0, n = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());for(int i = 1; i <= n; i++) {String[] xy = br.readLine().split(" ");info[i] = new node();info[i].x = Integer.parseInt(xy[0]);info[i].y = Integer.parseInt(xy[1]);}Arrays.sort(info,1, 1 + n, new cmp());for(int i = 1; i <= n; i++) {dp[i] = 1;for(int j = 1; j < i; j++) {if(info[j].y < info[i].y) {dp[i] = Math.max(dp[i],dp[j] + 1);}}}int ans =0;for(int i = 1; i <= n; i++) {ans = Math.max(ans,dp[i]);}System.out.println(ans);}
}
class node{int x,y;
}
class cmp implements Comparator<node>{@Overridepublic int compare(node o1, node o2) {return o1.x - o2.x;}}

显然上面的代码时间复杂度为O(n2)

显然是过不了的，那么我们就需要使用二分优化的LIS（Nlogn）
主要思想就是，在满足最长上升子序列的前提下，尽可能增大结尾的潜能
使用q[]数组存储所有不同长度的上升子序列的结尾的最小值。
每加进来一个数，通过在q中查找最大的小于ai的数，并将ai接上去，q[r+1]=a[i]

下面可以略：主要解释LIS的原理：

✍主要是因为，能接在更小的数后面的数肯定更多
比较绕的一点是，如果此时加入的数比结尾小，我们需要在q中查找大于等于它的数去替换，那么可能出现我们这个数比后买你的下标大 比如1 2 78
此时来了个5，我们需要用5替换7.但是显然5的下标肯定比7的大，但是这对于仅仅求最长上升子序列的长度是没有影响的，因为5后面的数的下标肯定是都大于5的，假如5后面没有数了，那么此时1
2 58
在序列里，所有最终答案为4，其实可以看作和5个7没有环保是等价的，我们将7换为5只是为了给后面造成更大的机会，比如5后买还有6，7，那么此时1
2 5 8，6进来找到8，进行替换为1 2 5 6然后7直接放后面 12 5 6
7这样就会比之前5和7不换序列更长。需要仔细体会！！！确实比较绕。

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (2e5 + 10);static node[] info = new node[N];static int k = 0, n = 0;static int[] q = new int[N];static int cnt = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());for(int i = 1; i <= n; i++) {String[] xy = br.readLine().split(" ");info[i] = new node();info[i].x = Integer.parseInt(xy[0]);info[i].y = Integer.parseInt(xy[1]);}Arrays.sort(info,1, 1 + n, new cmp());//		for(int i = 1; i <= n; i++) {
//			dp[i] = 1;
//			for(int j = 1; j < i; j++) {
//				if(info[j].y < info[i].y) {
//					dp[i] = Math.max(dp[i],dp[j] + 1);
//				}
//			}
//		}q[++cnt] = info[1].y;for(int i = 2; i <= n; i++) {if(info[i].y > q[cnt]) {q[++cnt] = info[i].y;}else {int tmp = find(info[i].y);q[tmp] = info[i].y;}}System.out.println(cnt);}//找最大的小于x的数:找>=x的第一个数private static int find(int x) {int l = 1, r = cnt;int res = -1;while(l <= r) {int mid = (l + r) >> 1;if(q[mid] >= x) {res = mid;r = mid - 1;}else {l = mid + 1;}}return res;}
}
class node{int x,y;
}
class cmp implements Comparator<node>{@Overridepublic int compare(node o1, node o2) {return o1.x - o2.x;}}

完美AC！

本质还是最长上升子序列，此时代表的是： dp[i]代表以a[i]结尾最大上升子序列和，
当a[j] < a[i]时候，我们改变之前的+1，为加当前这个数，注意是a[i]不是a[j]

public class Main{static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static int N = (int) (2e5 + 10);static int[] dp = new int[N]; //最长上升子序列static int k = 0, n = 0;static int[] q = new int[N];static int cnt = 0;public static void main(String[] args) throws Exception{n = Integer.parseInt(br.readLine());String[] aa = br.readLine().split(" ");for(int i = 1; i <= n; i++) {q[i] = Integer.parseInt(aa[i - 1]);}for(int i = 1; i <= n; i++) {dp[i] = q[i];for(int j = 1; j < i; j++){if(q[j] < q[i]) {dp[i] = Math.max(dp[i], dp[j] + q[i]);}}}int ans = 0;for(int i = 1; i <= n; i++) {ans = Math.max(ans,dp[i]);}System.out.println(ans);}
}

✍