[Leetcode] 300. Longest Increasing Subsequence

2023-02-24 131 words One minute

Contents

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

이것도 결국 개수를 구하는 거기 때문에 DP로 접근을 했다.

주어진 nums를 하나씩 보면서 지나온 배열의 최대 값을 저장하면서 진행

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))

    res := 0

    for i, num := range nums {
        max := 0
        maxIndex := 0

        for j := 0; j < i; j++ {

            if nums[j] < num && max < dp[j] {
                max = dp[j]
                maxIndex = j
            }
        }
        
        if max != 0 {
            dp[i] = dp[maxIndex] + 1
        } else {
            dp[i] = 1
        }

        if res < dp[i] {
            res = dp[i]
        }
    }

    return res
}