[백준] 11053.cpp : 가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

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

---

• 꼼꼼히 문제를 따지지 않으면 다양한 반례에 걸리기 쉬운 문제이다.
• 내 위치에서의 가장 긴 증가하는 부분 수열은, 이전까지의 가장 긴 증가하는 부분 수열에 1 (자기 자신)을 더한 값이다.
• 여기서 이전까지의 부분 수열들 중, 자기 자신보다 작은 값들의 수열들에 대해서만 고려해야 한다.
• 위의 로직을 매 반복마다 수행하기에는 O(n3) 이기 때문에, DP 배열을 만들어 이전의 값들을 담아놓기로 한다.

---

#include <iostream>

using namespace std;

int n;
int arr[1000];      // 입력받은 데이터
int ans[1000];      // 각 인덱스에 대한 최대 길이값을 담을 DP 배열

int main(void)
{
    cin >> n;

    for(int i = 0 ; i < n ; i++)
    {
        cin >> arr[i];
    }
    int answer = 0;
    for(int i = 0 ; i < n ; i++)                        // DP 배열 채움
    {
        int max = 0;
        for(int idx = 0 ; idx < i ; idx++)              // 이전까지의 배열들을 탐색
        {
            if(arr[idx] < arr[i] && ans[idx] > max)     // 자신보다 작은 입력값들 중, 최대 길이값을 찾음
            {
                max = ans[idx];
            }
        }
        ans[i] = max + 1;                               // 해당 길이값에 자기 자신을 추가하여 길이값 저장
        if(answer < ans[i]) answer = ans[i];            // 전체 길이값들 중 최댓값 갱신
    }

    cout << answer << endl;
}