1218. Longest Arithmetic Subsequence of Given Difference

1218. Longest Arithmetic Subsequence of Given Difference

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/

문제

풀이

Example 3을 예로 설명하면
arr = [1, 5, 7, 8, 5, 3, 4, 2, 1]이고 difference = -2

1. arr 마지막 원소부터 시작한다.
2. arr[i] + difference 가 dp안에 있으면 연결 할 수 있는 원소가 있다는 소리이고 없으면 해당 자신값인 1을 저장한다.
3. i = len(arr) - 1일 때 arr[i] = 1이고 dp에 -1값이 없으므로 1을 저장한다.
   dp[(1)] = 1
4. i = len(arr) - 2일 때 arr[i] = 2이고 dp에 0값이 없으므로 1을 저장한다.
   dp[(1)] = 1, dp[(2)] = 1
5. i = len(arr) - 3일 때 arr[i] = 4이고 dp에 2값이 있으므로 1+ dp[(2)] = 2를 저장한다.
   dp[(1)] = 1, dp[(2)] = 1, dp[(4)] = 2
   이렇게 해서 최대값을 구하는 방법이다.

결과