[Algorithm] 가장 긴 증가하는 부분 수열

[hwangJi-dev]

💬 문제

https://www.acmicpc.net/problem/11722

💬 Idea

• dp라는 배열을 만든다. 이 때 dp에는 각 값 별 가장 긴 부분수열의 길이가 저장된다.
• A를 돌면서 이전 인덱스들에 본인보다 작은 값이 있는지 검사한다.
• 만약 본인보다 작은 값이 있다면 해당 인덱스의 dp(가장 긴 부분수열의 길이) + 1 과 자기 자신 중 더 큰 값을 dp에 저장하며 갱신한다.
• dp의 가장 큰 값을 출력한다.

💬 풀이

import Foundation

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

solution11053()