[코드트리] 최대 증가 부분 수열 C++

문제

https://www.codetree.ai/missions/2/problems/longest-increasing-subsequence?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

계획 세우기

가장 작은 증가 부분 수열의 수는 1(증가하는 부분수열이 없을 경우 증가하는 부분 수열의 갯수는 1개이기 때문)

자기보다 앞에 있는 수들을 검사

작다면 그 수까지 있었던 증가 부분 수열의 갯수+1가 현재 dp에 저장된 수보다 크면 갱신

 

풀이

#include <iostream>

using namespace std;

int n;
int arr[1001];
int dp[1001];

int main() {
    // input
    cin >> n;
    for(int i=0; i<n; ++i){
        cin >> arr[i];
        dp[i]=1; //dp 1로 초기화
    }

    // solution
    for(int i=1; i<n; ++i){
        for(int j=0; j < i; ++j){
            if(arr[j]<arr[i]){
                dp[i]=max(dp[i], dp[j]+1);
            }
        }
    }
    

    // output
    int answer=1;
    for(int i=0; i<n; ++i){
        answer = max(answer, dp[i]);
    }

    cout << answer << '\n';
    return 0;
}