LWC 56:718. Maximum Length of Repeated Subarray

LWC 56:718. Maximum Length of Repeated Subarray

传送门:718. Maximum Length of Repeated Subarray

Problem:

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000

0 <= A[i], B[i] < 100

思路: 和上周一样,还是一道动态规划题,如果对动规不熟悉,可以采用递归+记忆化搜索,本题亦如此。首先判断末位两个元素是否相等,不相等把A的问题规模变成n-1,和B求出最长subarray长度,或者把B的问题规模变成m-1,和A求出最长subarray。

遇到相等该如何操作,自然在子问题n-1,和m-1基础上+1,(问题的定义如下:给定A和B的末区间i和j,返回A[0,…,i]和B[0,…,j]中以i和j结尾的最长subArray长度),

所以有如下递归式:

f(A, B, i, j) = 1 + f(A, B, i - 1, j - 1); if (A[i] == B[j])

or:
f(A, B, i, j) = 0;

此时就可以用数组dp记录每个状态的最长subArray长度,并在过程中不断更新max。

代码如下:

   public int findLength(int[] A, int[] B) {
        max = 0;
        int n = A.length;
        int m = B.length;
        dp = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; ++i) {
            for (int j = 0; j < m + 1; ++j) {
                dp[i][j] = -1;
            }
        }
        dfs(A, B, n - 1, m - 1);
        return max;
    }


    int[][] dp;
    int max = 0;
    int dfs(int[] A, int[] B, int n, int m) {
        if (n == -1 || m == -1) return 0;
        if (dp[n][m] >= 0) return dp[n][m];

        dfs(A, B, n - 1, m);
        dfs(A, B, n, m - 1);

        if (A[n] == B[m]) {
            int ans = 1;
            int sub = dfs(A, B, n - 1, m - 1);

            max = Math.max(max, ans + sub);
            dp[n][m] = ans + sub;
            return ans + sub;
        }
        else {
            dp[n][m] = 0;
            return 0;
        }
    }

注意此处,0也是可能的一种答案,所以DP初始化为-1,否则超时。

递推版本(动态规划):

        public int findLength(int[] A, int[] B) {
            int n = A.length;
            int m = B.length;
            int max = 0;
            int[][] dp = new int[n + 1][m + 1];

            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (A[i - 1] == B[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }

                    max = Math.max(dp[i][j], max);
                }
            }

            return max;
        }   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3435
来自专栏从流域到海域

《笨办法学Python》 第27课手记

《笨办法学Python》 第27课手记 本节课讲逻辑运算(即布尔运算),对于学过数字电路或者离散数学的人来说非常简单,甚至不需要去刻意记忆真值表。 逻辑运算只有...

18710
来自专栏杨建荣的学习笔记

大整数乘法的算法分析(r12笔记第42天)

昨天看了下Paxos协议,比我想象的要复杂。每次都没能耐着性子看完。但是隐隐感觉就跟钓鱼一般(尽管我没用真实试过),如果有耐性,能坚持还是能够明白的。 ...

2605
来自专栏小樱的经验随笔

浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

7607
来自专栏落影的专栏

程序员进阶之算法练习(十)2016CCPC东北重现赛

前言 最近几个月在做逻辑思维僵化的康复训练,刚好大学的教练说能争取到一个比赛的名额,于是兴致勃勃找了原来的队友和一个老学长,愉快的报名参加比赛。 于是开始...

3315
来自专栏CDA数据分析师

排序在数据分析中有多重要?

说不会对数据排序的举手,所有的手都放下了。拿到数据,谁还不会排序吗?就连你在打牌时都在排序。 ? 可是这一小小的操作,在数据分析中到底有...

1626
来自专栏前端儿

数数

我们平时数数都是喜欢从左向右数的,但是我们的小白同学最近听说德国人数数和我们有些不同,他们正好和我们相反,是从右向左数的。因此当他看到123时会说“321”。

823
来自专栏云时之间

python学习之文章数据分析

通常我们在进行NLP学习的时候,会经常的处理一些语料,同时也会对这些语料进行一些分析,今天的这篇文章我们通过分析quora上的Andrew NG的一个回答来实际...

3376
来自专栏大数据挖掘DT机器学习

[笔记]使用Python一步一步地来进行数据分析

原文 http://www.cnblogs.com/nxld/p/6058998.html 你已经决定来学习Python,但是你之前没有编程经验。因此,你常常...

6416
来自专栏趣学算法

算法之美——算法复杂性

《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

1161

扫码关注云+社区