718. Maximum Length of Repeated Subarray

718. Maximum Length of Repeated Subarray

https://leetcode.com/problems/maximum-length-of-repeated-subarray/

문제

처음 풀었던 답

처음 생각했던 DP테이블이다.

하지만 문제점이 있었는데 위에 같이 하게 되면 연속된 subarray가 아닌 불연속된 subarray의 최대값을 얻게 되었다.

두 번째 풀었던 답(Brute Force)

nums1에 원소를 nums2에 있는지 찾고 만약 있으면 nums1, nums2에 포인터를 이동시키며 총 이동된 길이의 최대값을 찾는 로직이다. 아무래도 최악의 경우에는 n^3이기에 TLE문제가 발생하였다.

세 번째 풀었던 답(DP)

연속된 subarray값을 찾기 위해서 전에 최대값을 계속 가져오는 것이 아니라 nums1[i], nums2[j]가 다르면 0을 저장하였더니 해결하였다.

결과(DP)