[C++] (백준 11053번) 가장 긴 증가하는 부분 수열

문제출처: 백준
문제 링크: https://www.acmicpc.net/problem/11053
난이도: ★★★☆☆

• 문제 분류: 다이나믹 프로그래밍 (DP)

[문제]

 

---

[분석]

n개의 원소를 배열에 저장한다.

배열의 맨 끝부터 맨 처음으로 내려오며 각각의 원소부터 시작하는 가장 긴 수열의 길이를 구하여 또다른 배열에 저장한다.

idx=n 부터 idx=0으로 진행할 때, 각 배열의 해당원소부터 배열의 끝까지 비교해 자신의 값보다 value가 크면서 가장 긴 수열의 길이를 가지고 배열의 값 +1의 값을 가진다. 자신의 원소에 대응하는 가장 긴 수열의 길이는 다른 배열에 직접 저장한다.

그후, 길이를 저장한 배열의 최대 값을 구해 해당 배열에서 나올 수 있는 가장 긴 수열의 길이를 가질 수 있게 한다.

간단한 식을 쓰면 다음과 같다. 

---

[코드]

#include <iostream>
using namespace std;

int arr[1001];
int max_len[1001];
int main() {
	int n;
	cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	
	int len=0;
	max_len[n-1]=1;
	for(int i=n-2;i>=0;i--){
	    int n_len=0;
	    for(int j=i+1;j<n;j++){
	        if((arr[i]<arr[j])&&(n_len<max_len[j])) n_len= max_len[j];
	    }
	    max_len[i]=n_len+1;
	
	}
	
	int real_max=max_len[0];
	for(int i=1;i<n;i++){
	    if(max_len[i]>real_max) real_max=max_len[i];
	}
	
    printf("%d\n",real_max);
}