최대 부분 증가 수열 [DP]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

입력예제 1
5 3 7 8 6 2 9 4

 

출력예제 1

4

풀이 

- 숫자 사이의 간격은 중요하지 않음(헷갈렸던 부분)

- 수열의 최대 길이가 이 문제에서 구하고자 하는 것이다.

- 수열을 구성할때는 1 2 3 4 처럼 마지막 수보다 앞의 수들이 작게 구성한다.

 

dy[1] = 5 , 길이 1

dy[2] = 3, 길이 1

dy[3] = 3,7 / 5, 7 , 길이 2

dy[4] = 8이기 때문에 앞에 7을 구성하는 길이+1(이때 1이 붙는 이유는 8이 하나 붙기 때문)이 된다, 길이 2+1 = 3

 

여기서 규칙을 찾으면

(1) 해당 인덱스에서 -1씩 감소하며 탐색

(2) 탐색한 값이 기준이 되는 수보다 작고(앞에 큰 수 불가능한 수열의 특징) , 가장 큰 값을 갖고 있으면

(3) 그 값에 +1한다.

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

//최대 증가 수열
int main()
{
    int n, res = 0;
    scanf("%d", &n);
    vector<int> arr(n + 1), dy(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dy[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int max = 0;
        for (int j = i - 1; j >= 1; j--)
        {
            if (arr[j] < arr[i] && max < dy[j])
            {
                max = dy[j];
            }
        }
        dy[i] = max + 1;
        if (dy[i] > res) res = dy[i];
    }
    printf("%d\n", res);
    return 0;
}