300. Longest Increasing Subsequence

 

문제

https://leetcode.com/problems/longest-increasing-subsequence/description/

입력

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

결과

ans:Int = 최장 증가 수열길이

해석

끝지점을 하나씩 늘려가면서, 최장 수열을 기록한다.

코드

ㅇclass Solution {
    func lengthOfLIS(_ nums: [Int]) -> Int {
        let n = nums.count
        if n == 1 {
            return 1 
        }

        var cache = [Int](repeating:0, count:n)
        var ans: Int = -1

        for i in 0..<n {
            cache[i] = 1
            let now = nums[i]
            if i == 0 { continue }
            for j in 0..<i {
                if nums[i] > nums[j] {
                    cache[i] = max(cache[i], cache[j] + 1)
                }
                ans = max(ans, cache[i])
            }
        }
        return ans
    }
}