前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定str1和str2两个字符串，求两个字符串的最长公共子数组，不是最长公共序列。
如：
str1:1AB2345CD str2:12345EF
结果：2345

解决方案

参考：https://swzhao.blog.csdn.net/article/details/127585231

原问题：
1、设计dp[i][j] 代表最长子数组以str1[i]和str2[j]结尾，最长子数组的长度
2、dp[i][j]的递推关系:如果需要求以str1[i]和str2[j]结尾的最长子数组长度，则首先判断str1[i] 和str2[j]是否相等，如果不相等，则dp[i][j]为0，如果相等，则dp[i][j] = dp[i-1][j-1] + 1

代码编写

java语言版本

原问题：
递归方法：

   
    /**
     * 获取最长子数组
     * @param str1
     * @param str2
     * @return
     */
    public static String getMaxSubArrCP(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] dp = new int[chars1.length][chars2.length];
        int[] maxIJ = getDpCP(chars1, chars2, dp);
        // 将最大值的坐标拿出来
        int maxI = maxIJ[0];
        int maxJ = maxIJ[1];
        int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
        int index = 0;
        char[] res = new char[maxLen];
        while (maxI >= 0 && maxJ >= 0) {
            if (chars1[maxI] == chars2[maxJ]) {
                res[index++] = chars1[maxI];
                maxI--;
                maxJ--;
            }else {
                break;
            }
        }
        CommonUtils.reverseChar(res, 0, index);
        return String.valueOf(res, 0, index);
    }

    /**
     * 生成dp矩阵
     * 返回最大值的两个坐标
     * @param chars1
     * @param chars2
     * @return
     */
    private static int[] getDpCP(char[] chars1, char[] chars2, int[][] dp) {
        // dp[i][j] 表示，chars[i]为底和chars[2]为底的公共子数组长度，区别于chars1[i]为底的，chars2[j]为底的数组的公共子数组长度
        //int[][] dp = new int[chars1.length][chars2.length];
        int maxI = 0;
        int maxJ = 0;
        int max = Integer.MIN_VALUE;
        dp[0][0] = chars1[0] == chars2[0] ? 1 : 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i][0] = dp[i-1][0] == 1 || chars1[i] == chars2[0] ? 1 : 0;
        }
        for (int j = 1; j < dp[0].length; j ++) {
            dp[0][j] = dp[0][j-1] == 0 || chars1[0] == chars2[j] ? 1 : 0;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (chars1[i] != chars2[j]) {
                    dp[i][j] = 0;
                }else {
                    int count = 1;
                    int iIndex = i;
                    int jIndex = j;
                    while (iIndex >= 0 && jIndex >= 0) {
                        if (chars1[iIndex] == chars2[jIndex]) {
                            count++;
                            iIndex--;
                            jIndex--;
                        }else {
                            break;
                        }
                    }
                    if (count > max) {
                        maxI = i;
                        maxJ = j;
                        max = count;
                    }
                    dp[i][j] = count;
                }
            }
        }
        return new int[]{maxI, maxJ};
    }

    /**
     * 降低空间复杂度版本
     * @param str1
     * @param str2
     * @return
     */
    private static String getMaxSubArrCPReduceMem(String str1, String str2) {
        if (str1 == null || str1.length() == 0
                || str2 == null || str2.length() == 0) {
            return null;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int max = Integer.MIN_VALUE;
        int maxI = 0;
        int maxJ = 0;
        int i = 0;
        int j = chars2.length-1;
        int count = chars1.length + chars2.length -1;
        while (count-- >= 0) {
            int temI = i;
            int temj = j;
            int temMax = 0;
            int temMaxI = 0;
            int temMaxJ = 0;
            int last = 0;
            while (temI < chars1.length && temj < chars2.length) {
                if (chars1[temI] == chars2[temj]) {
                    last++;
                }else {
                    last = 0;
                }
                if (last > temMax) {
                    temMax = last;
                    temMaxI = temI;
                    temMaxJ = temj;
                }
                temI++;
                temj++;
            }
            if (temMax > max) {
                maxI = temMaxI;
                maxJ= temMaxJ;
                max= temMax;
            }
            if (j != 0) {
                // 还在第一行
                j--;
            }else {
                i++;
            }
        }
        // 将最大值的坐标拿出来
        int maxLen = chars1.length > chars2.length ? chars1.length : chars2.length;
        int index = 0;
        char[] res = new char[maxLen];
        while (maxI >= 0 && maxJ >= 0) {
            if (chars1[maxI] == chars2[maxJ]) {
                res[index++] = chars1[maxI];
                maxI--;
                maxJ--;
            }else {
                break;
            }
        }
        CommonUtils.reverseChar(res, 0, index);
        return String.valueOf(res, 0, index);
    }

    public static void main(String[] args) {
        getMaxSubArrCPReduceMem("1AB2345CD", "12345EF");
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

首先想要理解这道题，可以参考一下

https://swzhao.blog.csdn.net/article/details/127526166

只读感悟即可，如果我没有感悟上一道题，这道题是不会做的，首先上道题把规律应该讲的比较清楚，这道题也是一道最优解不是dp最后一个元素类型的问题，那么很显然，同样的感觉 以每一个元素为底时的结果有可能不包含该元素，这个时候就需要强制将当前元素变成底来做动态规划，当我想到这个思路的时候这道题基本上就是秒了。

这里提一句降低空间复杂度的版本，这个最优解为什么能够产生呢？是因为子数组都是连续的，不像子序列，并且子数组str1和str2元素都是相等的，所以这个最优解的代表仅仅只需要子数组的头或者尾就可以了，因此整个过程就是求最优解的头或者尾就行了。