718. Maximum Length of Repeated Subarray

Table of Contents

  1. 問題
  2. 雛形
  3. 解き方
  4. コード

問題

718. Maximum Length of Repeated Subarray

整数配列 nums1, nums1 が与えられます。2 つの整数配列に共通する最も長い部分配列の長さを求めてください。

例えば nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7] のとき、どちらにも含まれる最も長い部分配列は [3, 2, 1] で 長さは 3 です。

雛形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <vector>
#include <gtest/gtest.h>
using namespace std;

class Solution
{
public:
    int findLength(vector<int> &nums1, vector<int> &nums2)
    {
        return 0;
    }
};

TEST(TestCase, Case1)
{
    auto s = Solution();
    auto nums1 = vector<int>{1, 2, 3, 2, 1};
    auto nums2 = vector<int>{3, 2, 1, 4, 7};
    auto actual = s.findLength(nums1, nums2);
    auto expected = 3;
    EXPECT_EQ(expected, actual);
}
TEST(TestCase, Case2)
{
    auto s = Solution();
    auto nums1 = vector<int>{0, 0, 0, 0, 0};
    auto nums2 = vector<int>{0, 0, 0, 0, 0};
    auto actual = s.findLength(nums1, nums2);
    auto expected = 5;
    EXPECT_EQ(expected, actual);
}

解き方

DP を使います。2 次元配列の変数 dp を定義し、dp[i+1][j+1] は nums1[i] と nums2[j] を選択したときの最も長い長さを表します。

以下は nums1 = [1, 2, 3, 2, 1], nums2 = [3, 2, 1, 4, 7] の例です。

  • nums1[2], nums2[0] のとき、長さは 1
  • nums1[3], nums2[1] のとき、長さは 2
    • これは1つ前の位置である nums1[2], num2[0] の値に 1 加えた結果
  • nums1[4], nums2[2] のとき、長さは 3
    • これは1つ前の位置である nums1[3], num2[1] の値に 2 加えた結果

つまり、以下のテーブルを作ります。

i
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 1 0 0
j 2 0 0 1 0 0 0
3 0 1 0 0 0 0
4 0 0 2 0 0 0
5 0 0 0 3 0 0

このテーブルに現れる最大の値 3 が、共通する部分配列の最大の長さです。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    int findLength(vector<int> &nums1, vector<int> &nums2)
    {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int answer = 0;
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                if (nums1[i] == nums2[j])
                {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                    answer = max(answer, dp[i + 1][j + 1]);
                }
            }
        }
        return answer;
    }
};