[LeetCode] 300. Longest Increasing Subsequence

문제

leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

 

코드

22년 2월 17일 코드

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var maxLength = 0
        var lengths = Array(repeating: 1, count: nums.count)
    
        for numIndex in 0..<nums.count {
            for lengthIndex in 0..<numIndex {
                if nums[lengthIndex] < nums[numIndex] {
                    lengths[numIndex] = max(lengths[numIndex], lengths[lengthIndex] + 1)
                }
            }
            maxLength = max(maxLength, lengths[numIndex])
        }
    
        return maxLength
    }
}

 

21년 4월 15일 코드

class Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var maxResult = 1
        var lis = [Int](repeating: 1, count: nums.count)
        for currentIndex in 0..<nums.count {
            for beforeIndex in 0..<currentIndex {
                if nums[beforeIndex] < nums[currentIndex] {
                    lis[currentIndex] = max(lis[currentIndex], lis[beforeIndex] + 1)
                    maxResult = max(maxResult, lis[currentIndex])
                } else if nums[beforeIndex] == nums[currentIndex] {
                    lis[currentIndex] = max(lis[currentIndex], lis[beforeIndex])
                }
            }
        }
        return maxResult
    }
}

설명

흔한 LIS입니다.

현재 인덱스 보다 이전 배열 값들을 훑어보고, 작은 값들을 찾는 로직으로 구현했습니다.

 

충격적인건, 작년에 구현한 코드의 속도가 17.5, 31.87%로 성능이 상당히 낮은 편이네요.

코드를 살펴보니, DP 방법이 있더라구요. 머리가 아파서 dp 알고리즘은 다음에 이어서 학습하겠습니다