首页 > 编程语言 > 详细

【力扣】最长重复子数组

时间:2020-07-01 21:45:01      阅读:46      评论:0      收藏:0      [点我收藏+]

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray

 解答方式:动态规划

技术分享图片

 

 

public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() == 0 || text2.length() == 0){
            return 0;
        }

        int max = 0;
        char textA[] = text1.toCharArray();
        char textB[] = text2.toCharArray();
        int dp[][] = new int[textA.length + 1][textB.length + 1];
        //最长公共子串 dp[i][j]=dp[i-1][j-1] + 1;
//        for (int i = 1;i< textA.length; i++){
//            for (int j = 1;j< textB.length; j++){
//                if (textA[i-1] == textB[j-1]){
//                    dp[i][j] = dp[i-1][j-1] + 1;
//                    max=Math.max(dp[i][j],max);
//                }else {
//                    dp[i][j]= 0;
//                }
//            }
//        }
//

        //最长公共子序列 dp[i][j] =
        for (int i = 1;i< textA.length; i++){
            for (int j = 1;j< textB.length; j++){
                if (textA[i-1] == textB[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j]= Math.max(dp[i-1][j],dp[i][j-1]);
                }
                max = Math.max(max,dp[i][j]);
            }
        }
        return max;
    }

 

【力扣】最长重复子数组

原文:https://www.cnblogs.com/fengtingxin/p/13221346.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!