Special sequences

You are given an array $A$ of length $N$ and array $B$ of length $M$.

A special sequence can be defined in either of the two ways:

• Sequence such that $a_1<b_1<a_2<b_2<$ and so on, where $a_1,a_2,a_3,..$ is a subsequence of array $A$ and $b_1,b_2,b_3,...$ is a subsequence of array $B$
• Sequence such that $b_1<a_1<b_2<a_2<$ and so on, where $a_1,a_2,a_3,..$ is a subsequence of array $A$ and $b_1,b_2,b_3,...$ is a subsequence of array $B$

Find the maximum length of a special sequence that can be formed.

Example:

Input:  n=4, m=2, A[] = { 2, 1, 3, 1 }, B[] = { 5, 2 }
Output: 3

Approach

Java

public class SpecialSequences {
    public static void main(String args[]) {
        n = 4;
        m = 2;
        int i;
        int A[] = { 2, 1, 3, 1 };
        int B[] = { 5, 2 };
        for (i = 0; i < n; i++)
            a[i] = A[i];
        for (i = 0; i < m; i++)
            b[i] = B[i];
        for (i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j][0] = dp[i][j][1] = -1;
        int ans = solve(0, 0, 1, -1000000);
        for (i = 0; i <= n; i++)
            for (int j = 0; j <= m; j++)
                dp[i][j][0] = dp[i][j][1] = -1;
        ans = Math.max(ans, solve(0, 0, 0, -1000000));
        System.out.println(ans);
    }

    static int N = 2005, dp[][][] = new int[N][N][2], n, m, a[] = new int[N], b[] = new int[N];

    static int solve(int i, int j, int t, int l) {
        if (i >= n && t == 0)
            return 0;
        if (j >= m && t == 1)
            return 0;
        if (i < n && j < m && dp[i][j][t] != -1)
            return dp[i][j][t];

        if (t == 0) {
            int rt = 0;
            if (a[i] > l)
                rt = 1 + solve(i + 1, j, t ^ 1, a[i]);
            rt = Math.max(rt, solve(i + 1, j, t, l));
            dp[i][j][t] = rt;
            return rt;
        } else {
            int rt = 0;
            if (b[j] > l)
                rt = 1 + solve(i, j + 1, t ^ 1, b[j]);
            rt = Math.max(rt, solve(i, j + 1, t, l));
            dp[i][j][t] = rt;
            return rt;
        }
    }

}