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 条评论
登录 后参与评论

相关文章

来自专栏JavaEE

mybatis的association以及collection的用法association:一对一关联(has one)collection:一对多关联(has many)

4278
来自专栏JavaQ

温故而知新-MySQL数据类型

选择数据类型的原则 MySQL支持多种数据类型,选择合适的数据类型存储数据对MySQL存储引擎来说至关重要,下面的一些原则可以在选择数据类型的时候做出更合适的选...

3027
来自专栏jeremy的技术点滴

实例变量的懒初始化

3154
来自专栏CodingToDie

MySql Hash 索引

Hash 索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 ...

2723
来自专栏开发与安全

从零开始学C++之对象的使用(三):static 与单例模式、auto_ptr与单例模式、const 用法小结、mutable修饰符

一、static 与单例模式 单例模式也就是简单的一种设计模式,它需要: 保证一个类只有一个实例,并提供一个全局访问点 禁止拷贝 #include <i...

1910
来自专栏Java后端技术

你敢说自己了解单例模式?

  最近在学习设计模式,在看到单例模式的时候,我一开始以为直接很了解单例模式了,实现起来也很简单,但是实际上单例模式有着好几个变种,并且多线程中涉及到线程安全问...

882
来自专栏Java帮帮-微信公众号-技术文章全总结

Oracle应用实战六——函数+集合

函数 字符函数 接收字符输入返回字符或者数值,dual是伪表 1. 把小写的字符转换成大小的字符 upper('smith') ? 2. 把大写字符变成小写字符...

2805
来自专栏跟着阿笨一起玩NET

sql server 获取每一个类别中值最大的一条数据

SELECT  * FROM    (           SELECT    * ,                     ROW_NUMBER() OVE...

1601
来自专栏Clive的技术分享

PHP实现单例模式

<?php /** * 单例模式实现 */ class Singleton { //静态变量保存全局实例 private static $ins...

2837
来自专栏性能与架构

Mysql 索引与排序

image.png sql 中 order by 排序可能发生2种情况: 1)对应覆盖索引,直接在索引上查询时,就是有序的,不需要另外处理排序 2)没有使用到索...

3176

扫码关注云+社区