[C++] DP - 최대 부분 증가수열

#include <iostream>
#include <algorithm>
using namespace std;

int arr[1001];
int dy[1001];
int main() {
    ios_base::sync_with_stdio(false);
    int N,num,res = 0;
    cin >> N;
    
    for(int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    
    dy[1] = 1;
    
    for(int i = 2; i <= N; i++){
        int max = 0; //0으로 해놓으면 아주 편함. 자기보다 작은 arr값이 없을때 else로 dy[i] = 1할 필요 없음
        for(int j = i-1; j >= 1; j--){
            if(arr[j]<arr[i] && dy[j] > max) //이전의 값을 모두 탐색할 것인데, 자기자신보다 작은 값들 중 길이가 가장 긴 값이 있다면 max에 저장한다
                max = dy[j];
        }
        //max에는 자신의값(arr[i])보다 작은 이전의 값(arr[j])들 중 길이가 가장 긴 값이 들어가있다.
        //자기 자신은 그 값보다 길이가 1증가해야하므로 dy에 값을 할당한다.
        dy[i] = max + 1; 
        if(dy[i]>res) res = dy[i];
    }
}

풀이

1. Dy Table을 정의한다. Dynamic Table의 index가 마지막 값일 때, 최대부분 증가수열의 최대 길이가 할당 됨

2. Bottom-Up 방식으로 Dy Table에 값을 할당한다.

3. 입력값을 살펴보면서 Dy Table에 어떤 값이 들어가야하는지 판단하며 규칙성을 알아낸다.

4. arr의 i for문을 돌면서 삽입정렬 자료구조처럼 j for문으로 이전 값들을 탐색한다. 

5. 자기 자신(arr[i])보다 작은 값(arr[j])이 있고 dy[j]가 기존의 max값 보다 크다면 dy[i] = max+1을 할당한다.

 예) i가 7이면 j = 6~1이다. 모든 arr[j]는 arr[i]보다 작은데, 결국 max값에는 3이 할당될 것이다. 그러므로 dy[i] = 3+1인 4가  들어간다.

 

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard