[백준 11053] 가장 긴 증가하는 수열

문제

링크

풀이

W[n] : n 번째에 위치해있는 정수

1	2	3	4	5	6
10	20	10	30	20	50

D[n] : n의 위치에서 끝나는 최장 길이 수열

k : 0 ~ n - 1까지의 수라고 정의할 때
W[k] < W[n] 일 경우
D[n] = max(D[n], D[k] + 1)로 갱신한다

코드

func solve() {
    let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
    
    var dp = [Int](repeating: 1, count: arr.count)
    
    for i in 0 ..< arr.count {
        for j in 0 ..< i {
            if arr[i] > arr[j] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    
    print(dp.max()!)
}