718. Maximum Length of Repeated Subarray

leetcode medium

#array#csharp#dynamic-programming#leetcode#math#medium#search

Task

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

Output: 3

C# solution

matched/original

public class Solution {
    public int FindLength(int[] nums1, int[] nums2) {
        int[,] dp = new int[nums1.Length + 1, nums2.Length + 1];
        int maxLength = 0;
        for (int i = nums1.Length - 1; i >= 0; i--) {
            for (int j = nums2.Length - 1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    dp[i, j] = dp[i + 1, j + 1] + 1;
                    maxLength = Math.Max(maxLength, dp[i, j]);
                }
            }
        }
        return maxLength;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindLength(vector<int>& nums1, vector<int>& nums2) {
        int[,] dp = new int[nums1.size() + 1, nums2.size() + 1];
        int maxLength = 0;
        for (int i = nums1.size() - 1; i >= 0; i--) {
            for (int j = nums2.size() - 1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    dp[i, j] = dp[i + 1, j + 1] + 1;
                    maxLength = max(maxLength, dp[i, j]);
                }
            }
        }
        return maxLength;
    }
}

Java solution

matched/original

public class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int maxLength = 0;
        for (int i = nums1.length - 1; i >= 0; i--) {
            for (int j = nums2.length - 1; j >= 0; j--) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    maxLength = Math.max(maxLength, dp[i][j]);
                }
            }
        }
        return maxLength;
    }
}

JavaScript solution

matched/original

var findLength = function(nums1, nums2) {
    let dp = Array(nums1.length + 1).fill(0).map(() => Array(nums2.length + 1).fill(0));
    let maxLength = 0;
    for (let i = nums1.length - 1; i >= 0; i--) {
        for (let j = nums2.length - 1; j >= 0; j--) {
            if (nums1[i] === nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                maxLength = Math.max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
};

Python solution

matched/original

def findLength(nums1, nums2):
    dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
    max_len = 0
    for i in range(len(nums1) - 1, -1, -1):
        for j in range(len(nums2) - 1, -1, -1):
            if nums1[i] == nums2[j]:
                dp[i][j] = dp[i + 1][j + 1] + 1
                max_len = max(max_len, dp[i][j])
    return max_len

Go solution

matched/original

package main

func findLength(nums1 []int, nums2 []int) int {
    dp := make([][]int, len(nums1) + 1)
    for i := range dp {
        dp[i] = make([]int, len(nums2) + 1)
    }
    maxLength := 0
    for i := len(nums1) - 1; i >= 0; i-- {
        for j := len(nums2) - 1; j >= 0; j-- {
            if nums1[i] == nums2[j] {
                dp[i][j] = dp[i + 1][j + 1] + 1
                if dp[i][j] > maxLength {
                    maxLength = dp[i][j]
                }
            }
        }
    }
    return maxLength
}

Explanation

Algorithm

Создайте двумерный массив для хранения длин общих подмассивов.

Используйте динамическое программирование для нахождения максимальной длины общего подмассива.

Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.

😎