[알고리즘] 최대 부분 증가수열

문제 내용

• N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가수열을 만들 수 있다.

구현 방식

• acc[k] 는 현재 k 번째 원소를 마지막으로 택해서 만들었을 때 올 수있는 최대 부분 증가 수열을 의미한다.
• acc[k] 는 k 번째 이전의 원소들 중에서 ,
  • k 번째 원소 보다 작으면서 최대 부분 증가 수열이 가장 큰 경우를 택했을 때가 해당된다.
• 점화식으로 나타내면 acc[k] = MAX( acc[i] + 1 ) (i 는 0~ k-1 까지, acc[i] < acc[k])

int DP(int N, vector<int>& numbers)
{
    vector<int> acc = vector<int>(N, 1);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (numbers[i] > numbers[j])
                acc[i] = max(1 + acc[j], acc[i]);
        }
    }
    return *max_element(acc.begin(), acc.end());
}