目录

DP:最长上升子序列模型

现在打算写一些短点的文章了,LeetCode 系列不会再 append 了,如果写 lc 题会单独开一篇文章,然后写题解

最长上升子序列模型

300. 最长上升子序列

673. 最长递增子序列的个数

1016. 使序列递增的最小交换次数(LintCode)

354. 俄罗斯套娃信封问题

LIS 有 N^2 的 DP 解法,也有 NlogN 的贪心的解法,具体用那种取决于数据范围

1017. 怪盗基德的滑翔翼

怪盗基德是一个充满传奇色彩的怪盗,专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方,就是他每次都能逃脱中村警部的重重围堵,而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天,怪盗基德像往常一样偷走了一颗珍贵的钻石,不料却被柯南小朋友识破了伪装,而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。

不得已,怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有 N 幢建筑排成一条线,每幢建筑的高度各不相同。

初始时,怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑,但是不能中途改变方向(因为中森警部会在后面追击)。

因为滑翔翼动力装置受损,他只能往下滑行(即:只能从较高的建筑滑翔到较低的建筑)。

他希望尽可能多地经过不同建筑的顶部,这样可以减缓下降时的冲击力,减少受伤的可能性。

请问,他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)?

输入格式

输入数据第一行是一个整数 K,代表有 K 组测试数据。

每组测试数据包含两行:第一行是一个整数 N,代表有 N 幢建筑。第二行包含 N 个不同的整数,每一个对应一幢建筑的高度 h,按照建筑的排列顺序给出。

输出格式

对于每一组测试数据,输出一行,包含一个整数,代表怪盗基德最多可以经过的建筑数量。

数据范围

1≤K≤100, 1≤N≤100, 0<h<10000

输入样例:

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例:

6
9

解法一

常规 N^2 动态规划的方式 & NlogN 贪心解法(NlogN 的解法回忆了一会儿才推出来,如果数据范围不是很大还是 N^2 的 dp 好写)

import java.io.*;
import java.util.*;
//AcWing 1017. 怪盗基德的滑翔翼 https://www.acwing.com/problem/content/1019/
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int[] w = new int[n];
            for (int i = 0; i < n; i++) {
                w[i] = sc.nextInt(); 
            }
            System.out.println(Math.max(solve(w, n), solve(reverse(w), n))); 
        }
    }

    //DP(N^2) 的解法
    public static int solve(int[] w, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (w[j] > w[i]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);  
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res; 
    }

    //tail[i]: 长度为 i 的递减子序列最大结尾
    public static int solve2(int[] w, int n) {
        int[] tail = new int[n];
        int len = 0;
        for (int i = 0; i < n; i++) {
            int idx = search(tail, len, w[i]);
            if (idx == -1) {
                tail[len++] = w[i];
            } else {
                tail[idx] = w[i];
            }
        }
        return len;
    }

    //从左到右找第一个小于 target 的元素下标,替换它,使得结尾更大,长度更长
    public static int search(int[] tail, int len, int target){
        int left = 0, right = len-1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (tail[mid] <= target) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }

    public static int[] reverse(int[] w) {
        for (int i = 0, j = w.length-1; i < j; i++, j--) {
            int temp = w[i];
            w[i] = w[j];
            w[j] = temp;
        }
        return w;
    }
}

1014. 登山

五一到了,ACM 队组织大家去登山观光,队员们发现山上一个有 N 个景点,并且决定按照顺序来浏览这些景点,即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯,就是不连续浏览海拔相同的两个景点,并且一旦开始下山,就不再向上走了。

队员们希望在满足上面条件的同时,尽可能多的浏览景点,你能帮他们找出最多可能浏览的景点数么?

输入格式

第一行包含整数 N,表示景点数量。

第二行包含 N 个整数,表示每个景点的海拔。

输出格式

输出一个整数,表示最多能浏览的景点数。

数据范围 2≤N≤1000 输入样例:

8
186 186 150 200 160 130 197 220

输出样例:

4

解法一

LIS 转换了一下而已,求每个点从左到右 和 从右到左的最长上升子序列最大和就 ok 了

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] w = new int[N];
        for (int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
        }
        System.out.println(solve(w, N));
    }

    //186 186 150 200 160 130 197 220  := 4
    public static int solve(int[] w, int N) {
        int[] dp1 = new int[N];
        int[] dp2 = new int[N];
        Arrays.fill(dp1, 1);
        Arrays.fill(dp2, 1);
        int res = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (w[j] < w[i]) {
                    dp1[i] = Math.max(dp1[j]+1, dp1[i]);          
                }
            }
        }
        for (int i = N-1; i >= 0; i--) {
            for (int j = N-1; j > i; j--) {
                if (w[j] < w[i]) {
                    dp2[i] = Math.max(dp2[j]+1, dp2[i]);          
                }
            }
            res = Math.max(res, dp1[i]+dp2[i]-1);
        }
        return res;
    }
}

482. 合唱队形 和这一题一样,不重复写了

1012. 友好城市

Palmia 国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的 N 个城市。

北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。

每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政府决定避免任意两条航道交叉,以避免事故。

编程帮助政府做出一些批准和拒绝申请的决定,使得在保证任意两条航线不相交的情况下,被批准的申请尽量多。

输入格式

第 1 行,一个整数 N,表示城市数。

第 2 行到第 n+1 行,每行两个整数,中间用 1 个空格隔开,分别表示南岸和北岸的一对友好城市的坐标。

输出格式

仅一行,输出一个整数,表示政府所能批准的最多申请数。

数据范围

1≤N≤5000, 0≤xi≤10000

输入样例:

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例:

4

解法一

和之前的 354. 俄罗斯套娃信封问题 一样,还简单一点,坐标都是唯一的,不需要考虑坐标重合的问题,具体可以去看看俄罗斯套娃的这个题

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] w = new int[N][2];
        for (int i = 0; i < N; i++) {
            w[i][0] = sc.nextInt();
            w[i][1] = sc.nextInt();
        }
        System.out.println(solve2(w, N));
    }

    //5000 * 5000 = 2500 0000,能过但是有点慢
    public static int solve(int[][] w, int N) {
        Arrays.sort(w, (w1, w2)->w1[0]-w2[0]);
        int res = 1;
        int[] dp = new int[N];
        for (int i = 0; i < N; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (w[j][0] < w[i][0] && w[j][1] < w[i][1]) {
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    //NlogN 贪心二分的做法
    public static int solve2(int[][] w, int N) {
        Arrays.sort(w, (w1, w2)->w1[0]-w2[0]);
        int[] tail = new int[N];
        int len = 0;
        for (int i = 0; i < N; i++) {
            int idx = search(tail, len, w[i][1]);
            if (idx == -1) {
                tail[len++] = w[i][1];
            } else {
                tail[idx] = w[i][1];
            }
        }
        return len;
    }

    //从左到右找第一个大于 target 的,后面替换它,使得结尾更小
    public static int search(int[] tail, int len, int target) {
        int left = 0, right = len-1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (tail[mid] > target) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
}

1016. 最大上升子序列和

一个数的序列 bi,当 b1<b2<…<bS 的时候,我们称这个序列是上升的。

对于给定的一个序列 (a1,a2,…,aN),我们可以得到一些上升的子序列 (ai1,ai2,…,aiK),这里 1≤i1<i2<…<iK≤N。

比如,对于序列 (1,7,3,5,9,4,8),有它的一些上升子序列,如 (1,7),(3,4,8) 等等。

这些子序列中和最大为 18,为子序列 (1,3,5,9) 的和。

你的任务,就是对于给定的序列,求出最大上升子序列和。

注意,最长的上升子序列的和不一定是最大的,比如序列 (100,1,2,3) 的最大上升子序列和为 100,而最长上升子序列为 (1,2,3)。

输入格式

输入的第一行是序列的长度 N。

第二行给出序列中的 N 个整数,这些整数的取值范围都在 0 到 10000(可能重复)。

输出格式

输出一个整数,表示最大上升子序列和。

数据范围

1≤N≤1000

输入样例:

7
1 7 3 5 9 4 8

输出样例:

18

解法一

没啥好说的,比较简单

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] w = new int[N];
        for (int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
        }
        System.out.println(solve(w, N));
    }

    public static int solve(int[] w, int N) {
        int[] dp = new int[N];
        int res = 0;
        for (int i = 0; i < N; i++) {
            dp[i] = w[i];
            for (int j = 0; j < i; j++) {
                if (w[j] < w[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+w[i]);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

1010. 拦截导弹

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。

某天,雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数,导弹数不超过 1000),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式:

共一行,输入导弹依次飞来的高度。

输出格式:

第一行包含一个整数,表示最多能拦截的导弹数。

第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。

输入样例:

389 207 155 300 299 170 158 65

输出样例:

6
2

解法一

Dilworth 定理,双 DP 解法

//300 250 275 252 200 138 245 := 5,2
//最多击落多少就不多说了
//最少需要的系统数量实际上就是最长上升子序列的个数,这里涉及到 Dilworth 定理
public static int[] solve(int[] w, int N){
    int[] down = new int[N];
    int[] up = new int[N];
    int max = 0, count = 1;
    for (int i = 0; i < N; i++) {
        up[i] = down[i] = 1;
        for (int j = 0; j < i; j++) {
            if (w[j] >= w[i]) {
                down[i] = Math.max(down[j]+1, down[i]);
            } else {
                up[i] = Math.max(up[j]+1, up[i]);
            }
        }
        max = Math.max(max, down[i]);
        count = Math.max(count, up[i]);
    }
    return new int[]{max, count};
}

最多击落多少就不多说了,最少需要的系统数其实就是最长上升子序列,因为这个子序列是必不可能在同一套系统中被击落,当遇到这个子序列中的元素的时候,就需要增加一套系统,所以最少就是这个子序列的长度

最少需要的系统数量(最少的覆盖整个序列的不上升序列个数)就是最长的上升子序列长度,涉及到 Dilworth 定理(导弹拦截问题与 Dilworth 定理),感兴趣可以去了解下,定理的定义为:对于任意有限偏序集,其最大反链中元素的数目必等于最小链划分中链的数目

本题中,最少需要的导弹系统数量就是最小链划分中链的数量,其最大反链就是最长上升子序列长度,所以直接求最长上升子序列的长度就 ok 了

解法二

双贪心解法。

①求 LIS 的贪心做法,tail[j]表示长度为j的下降序列,每个w[i]作为结尾的时候优先选择大于w[i]的最小的tail[j](也就是从左到右最第一个大于 w[i] 的),然后接在它后面,这样让长度为 j 的下降序列结尾变小,后面可以接上更多的元素,使得序列可以更长,并且这样不会影响之前已有的序列关系,最终 tail 的长度就是最长上升子序列的长度

②求最少的覆盖全序列的下降子序列个数,tail[j]表示目前为止第j个系统的最大结尾元素,每个w[i]被遍历到的时候都是作为某一个系统的结尾,那么此时就会面临选择,这个时候我们就可以贪心的将其放置到大于w[i]的最小的 tail 后面,这样避免浪费其他较大的结尾(结尾越大,后面可以接的导弹越多),选择消耗一个最小的结尾,可能有点抽象,举个例子就明白了 https://i.loli.net/2020/11/23/VY6nU9oFuaB3GkO.png

这里 1 就面临两个选择,要么接在 2 后面,要么接在 4 后面,很明显这里应该接在 2 后面,如果接在 3 后面那么后面的 3 就只能新建一个系统,会增加系统数量

具体的证明可以采用微调法,证明贪心解是小于等于最优解的,这里不再展开

//9 8 7 9 8 7 9 8 7 55 66 99 88 77 88 963 365 4561
//双贪心写法
public static int[] solve2(int[] w, int N){
    int[] res = new int[2];
    //长度为 i 的最长下降子序列的最小结尾
    int[] tail = new int[N];
    int len = 0;
    //最长下降子序列(不严格)
    for (int i = 0; i < w.length; i++) {
        //找 tail 中第一个小于 w[i] 的替换掉,这样后面可以接更多的数
        //可以二分优化下,这里就不写了
        int idx;
        for (idx = 0; idx < len; idx++) {
            if (tail[idx] < w[i]) {
                break;
            }
        }
        tail[idx] = w[i];
        len += (idx == len) ? 1 : 0;
    }
    res[0] = len;
    tail = new int[N];
    len = 0;
    //最少覆盖全序列的下降子序列个数
    for (int i = 0; i < w.length; i++) {
        //找 tail 中第一个大于等于 w[i] 的替换掉
        //可以二分优化下,这里就不写了
        int idx;
        for (idx = 0; idx < len; idx++) {
            if (tail[idx] >= w[i]) {
                break;
            }
        }
        tail[idx] = w[i];
        len += (idx == len) ? 1 : 0;
    }
    res[1] = len;
    return res;
}

187. 导弹防御系统

为了对抗附近恶意国家的威胁,R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如,一套系统先后拦截了高度为 3 和高度为 4 的两发导弹,那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。

输入格式

输入包含多组测试用例。

对于每个测试用例,第一行包含整数 n,表示来袭导弹数量。

第二行包含 n 个不同的整数,表示每个导弹的高度。

当输入测试用例 n=0 时,表示输入终止,且该用例无需处理。

输出格式

对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。

数据范围: 1≤n≤50

输入样例:

5
3 5 2 4 1
0 

输出样例:

2
样例解释
对于给出样例,最少需要两套防御系统。

一套击落高度为 3,4 的导弹,另一套击落高度为 5,2,1 的导弹。

解法一

搜索 + 贪心剪枝,搜索的复杂度是 O(N*2^N),每个位置有两种选择,每次选择都需要遍历 up 或者 down,虽然时间复杂度很高,但是整体的结果比较小,所以很多情况都被剪掉了,整体速度还不错

import java.util.*;
import java.io.*;
//1. 考虑每个点是在上升序列中还是下降序列中
//2. 考虑是否需要新建一个单独的序列
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int N = sc.nextInt();
            if (N == 0) return;
            int[] w = new int[N];
            up = new int[N];
            down = new int[N];
            res = Integer.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                w[i] = sc.nextInt();
            }
            dfs(w, 0, 0, 0);
            System.out.println(res);
        }
    }

    static int[] up = null;
    static int[] down = null;
    static int res;

    public static void dfs(int[] w, int c, int ul, int dl) {
        //关键的剪枝
        if (ul+dl >= res) return;
        if (c == w.length) {
            res = Math.min(ul+dl, res);
            return;
        }
        //将 c 放在上升序列中
        boolean flag = false;
        for (int i = 0; i < ul; i++) {
            if (up[i] > w[c]) {
                flag = true;
                int temp = up[i];
                up[i] = w[c];
                dfs(w, c+1, ul, dl);
                up[i] = temp;
                break;
            }
        }
        if (!flag) {
            up[ul] = w[c];
            dfs(w, c+1, ul+1, dl);
            up[ul] = 0;
        }
        flag = false;
        for (int i = 0; i < dl; i++) {
            if (down[i] < w[c]) {
                flag = true;
                int temp = down[i];
                down[i] = w[c];
                dfs(w, c+1, ul, dl);
                down[i] = temp;
                break;
            }
        }
        if (!flag) {
            down[dl] = w[c];
            dfs(w, c+1, ul, dl+1);
            down[dl] = 0;
        }
    }
}

解法二

迭代加深搜索,代码简化,在解比较小的时候可以使用这种搜索方式找最小值,结合了 DFS 和 BFS 的优点

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
        int N = sc.nextInt();
        if (N == 0) return;
        int[] w = new int[N];
        up = new int[N];
        down = new int[N];
        res = Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            w[i] = sc.nextInt();
        }
        //dfs(w, 0, 0, 0);
        int depth = 0;
        while (!dfs(w, depth, 0, 0, 0)) {
            depth++;
        }
        System.out.println(depth);
    }
}

static int[] up = null;
static int[] down = null;
//迭代加深,BFS 版的 DFS
public static boolean dfs(int[] w, int depth, int c, int ul, int dl) {
    if (ul+dl > depth) return false;
    if (c == w.length) {
        return true;
    }
    //将 c 放在上升序列中,那么我们应该找到小于 w[i] 的最大的 tail
    int i = 0;
    for (i = 0; i < ul; i++) {
        if (up[i] < w[c]) break;
    }
    int temp = up[i];
    up[i] = w[c];
    if (i == ul) {
        if (dfs(w, depth, c+1, ul+1, dl)) {
            return true;      
        }
    } else if (dfs(w, depth, c+1, ul, dl)) {
        return true;
    }
    up[i] = temp;
    //将 c 放在下降序列中,那么我们应该找到大于 w[i] 的最小的 tail
    for (i = 0; i < dl; i++) {
        if (down[i] > w[c]) break;
    }
    temp = down[i];
    down[i] = w[c];
    if (i == dl) {
        if (dfs(w, depth, c+1, ul, dl+1)) {
            return true;
        }
    } else {
        if (dfs(w, depth, c+1, ul, dl)) {
            return true;
        }
    }
    down[i] = temp;
    return false;
}

272. 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列,再让他们研究了最长公共子序列,现在又让他们研究最长公共上升子序列了。

小沐沐说,对于两个数列 A 和 B,如果它们都包含一段位置不一定连续的数,且数值是严格递增的,那么称这一段数是两个数列的公共上升子序列,而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂,小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过,只要告诉奶牛它的长度就可以了。

数列 A 和 B 的长度均不超过 3000。

输入格式

第一行包含一个整数 N,表示数列 A,B 的长度。

第二行包含 N 个整数,表示数列 A。

第三行包含 N 个整数,表示数列 B。

输出格式

输出一个整数,表示最长公共上升子序列的长度。

数据范围

1≤N≤3000, 序列中的数字均不超过 2^31−1

输入样例:

4
2 2 1 3
2 1 2 3

输出样例:

2

解法一

朴素的解法应该自己想出来的,可惜,没想出来,看了解答才理解,这里dp[i][j] 是指** A 序列的前 i 个字符和 B 的前 j 个字符组成的,以B[j]结尾的最长公共上升子序列长度**,实际上是 lcs 个 lis 的完美结合,因为状态定义指定了B[j]是一定要包含的,所以相比 LCS 的四种情况,这里只有两种情况,包含或者不包含A[i]

  • 不包含 A[i] 那么状态就是dp[i-1][j];
  • 如果要包含 A[i],那么A[i]必须等于B[j],否则就没有考虑的意义,然后我们按照 LIS 的方法去找一个最大值就 ok 了

时间复杂度 N^3,这里按道理是会被卡掉的,但是并没有。..

import java.util.*;
import java.io.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = sc.nextInt();
        }
        System.out.println(solve(A, B, N));
    }

    public static int solve(int[] A, int[] B, int N){
        //A 前 i 个字符和 B 前 j 个字符并且以 B[j] 结尾的最长 LCIS
        int[][] dp = new int[N+1][N+1];
        int res = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i-1][j];
                if (A[i-1] == B[j-1]) {
                    dp[i][j] = Math.max(dp[i][j], 1);
                    for (int k = 1; k < j; k++) {
                        if (B[j-1] > B[k-1]) {
                            dp[i][j] = Math.max(dp[i][k]+1, dp[i][j]);
                        }
                    }
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }
}

解法二

对上面的解法做了等价变形,首先上面解法内循环是找[1,j-1]区间内B[k]<B[j]的最大值,同时此时的B[j]==A[i],所以我们可以进行一波等价变形,动态的计算这个最大值,从而优化掉一层循环,还是很巧妙的

//代码等价变形,时间复杂度 N^2
public static int solveOpt(int[] A, int[] B, int N){
    //A 前 i 个字符和 B 前 j 个字符并且以 B[j] 结尾的最长 LCIS
    int[][] dp = new int[N+1][N+1];
    int res = 0;
    for (int i = 1; i <= N; i++) {
        int maxv = 1;
        for (int j = 1; j <= N; j++) {
            dp[i][j] = dp[i-1][j];
            if (A[i-1] == B[j-1]) {
                dp[i][j] = Math.max(dp[i][j], maxv);
            }
            if (B[j-1] < A[i-1]) {
                maxv = Math.max(maxv, dp[i][j]+1);
            }
            res = Math.max(res, dp[i][j]);
        }
    }
    return res;
}