[LIS, DP] BOJ 11053 가장 긴 증가하는 부분 수열 (C++)

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

11053번: 가장 긴 증가하는 부분 수열

 

문제 해결 알고리즘

 

다이나믹 프로그래밍을 이용해 푼 LIS알고리즘

 

https://kimmessi.tistory.com/191?category=871925 

[알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력

 

자세한 내용은 위의 링크를 참고

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int num; cin >> num;
    vector<int> v(num);
    vector<int> dp(num);
    int result = 1;
    for(int i=0;i<num;i++) cin >> v[i];

    dp[0] = 1;

    for(int i=1;i<num;i++){
        dp[i] = 1;
         for(int j=0;j<i;j++){    
            if(v[i] > v[j] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
        }
        result = max(result, dp[i]);
    }

    cout << result;
}