Daily LeetCode Challenge - 1027. Longest Arithmetic Subsequence

Problem From.

https://leetcode.com/problems/longest-arithmetic-subsequence/

오늘 문제는 array nums 가 주어졌을때, 그 안에서 가장 길이가 긴 등차수열을 찾는 문제였다.

이 문제는 DP 를 사용하여 풀 수 있었는데, 각각의 경우마다 다음 원소를 검사해나가면서 그 차이를 계속 저장해주면 되었다.
먼저 각각의 인덱스와 각 숫자의 차이를 저장해둘 배열을 만들어주고, 그 안에 hashMap 을 만들어둔다. 그리고 nums 에서 각각의 원소를 검사해나가면서 hashMap 에 조건에 맞는 원소를 추가해주고, 마지막에 map 의 길이를 통해서 비교하여 가장 긴 길이를 찾아주면 되었다.

class Solution {
    fun longestArithSeqLength(nums: IntArray): Int {
        val memo = Array<HashMap<Int, Int>>(nums.size) { hashMapOf() }

        var maxLength = 0

        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                val different = nums[i] - nums[j]
                memo[i][different] = (memo[j][different] ?: 1) + 1
                maxLength = maxLength.coerceAtLeast(memo[i][different]!!)
            }
        }

        return maxLength
    }
}