#11053번 가장 긴 증가하는 부분 수열 (C++)

링크 : www.acmicpc.net/problem/11053

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

 

이 문제는 영문명 'Longest Increaseing Subsequence (LIS)'로 잘 알려진 문제이다.

 

#include <iostream>
#include <algorithm>
#define MAX 1001
using namespace std;

int arr[MAX], sum[MAX], n = 0, ans = 1;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        sum[i] = 1;
    }
    for(int i=1; i<n; i++){
        for(int j=0; j<i; j++){
            if(arr[i]>arr[j]){
                if(sum[i]<sum[j]+1) sum[i] = sum[j] + 1;
            }
        }
        if(ans<sum[i]) ans = sum[i];
    }
    cout << ans << "\n";
    return 0;
}

참고로 어떤 수건 부분집합의 증가하는 최대값으로 1을 가질 수 있으므로, 디폴트 정답을 1로 설정해야 맞을 수 있다.