返回两个数组中相同数字不相交的最大连线数

        //给定两数组
        int[] a = {2, 5, 1, 2, 5};
        int[] b = {10, 5, 2, 1, 5, 2};
        //输出：3
        int[] a1 = {1, 2, 3};
        int[] b1 = {1, 3, 2};
        //输出：2
        int[] a2 = {2, 5, 1, 2, 5, 1, 3};
        int[] b2 = {10, 5, 2, 7, 5, 3, 3};
        //输出：4

答案：

   /**
         * 返回两个数组中相同数字不相交的最大连线数
         *
         * @param A int整型一维数组 整数集合A
         * @param B int整型一维数组 整数集合B
         * @return int整型
         */
        //暴力
        public int maxUncrossedLines(int[] A, int[] B) {
            int max = 0;
            for (int i = 0; i < A.length; i++) {
                int ti = i;
                int cnt = 0;
                int j = 0;
                while (ti < A.length && j < B.length) {
                    if (A[ti] == B[j]) {
                        cnt++;
                        ti++;
                    }
                    j++;
                }
                max = max > cnt ? max : cnt;
            }
            return max;
        }

        //dp[][]
        public int maxUncrossedLines2(int[] A, int[] B) {
            int alen = A.length;
            int blen = B.length;
            int max = 0;
            //dpij 代表从0-i,0-j的相同数字不相交的最大连线数
            int[][] dp = new int[alen + 1][blen + 1];
            if (A[0] == B[0])
                dp[0][0] = 1;
            for (int i = 1; i < alen; i++) {
                for (int j = 1; j < blen; j++) {
                    if (A[i] == B[j])
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            for (int i = 0; i < alen; i++) {
                for (int j = 0; j < blen; j++) {
                    System.out.printf(" " + dp[i][j]);
                }
                System.out.println();
            }
            return max;
        }

        //递归
        public int maxUncrossedLines3(int[] A, int[] B) {
            return helper(A, B, 0, 0);
        }

        public int helper(int[] a, int[] b, int i, int j) {
            if (i >= a.length || j >= b.length) {
                return 0;
            }
            if (a[i] == b[j])
                return helper(a, b, i + 1, j + 1) + 1;
            return Math.max(helper(a, b, i, j + 1), helper(a, b, i + 1, j));
        }