[c++] 최대부분 증가수열

최대부분 증가수열

#include<bits/stdc++.h>
using namespace std;
//int dy[1001], a[1001];
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, j, res=-2147000000;
	cin >> n;
	vector<int> dy(n+1), a(n+1);
	for(int i=1; i<=n; i++){
		cin >> a[i];
	}
	dy[1]=1;
	for(int i=2; i<=n; i++){
		int max=0;
		for(j=1; j<i; j++){		
			if(a[j]<a[i] && dy[j]>max) max=dy[j];
		}
		dy[i]=max+1;
		if(dy[i]>res) res=dy[i];	
	}
	cout<<res;
	return 0;
}

가장 길게증가하는 원소들을 뽑아서 길이가 최대인 부분 증가수열을 만들어서 

부분증가수열의 최대 길이를 출력하는 문제이다.

 

이 문제는 dp접근법을 사용해서 푸는 문제로 

첫번째 항부터 시작해서 각각의 항이 마지막이 되는 경우를 고려해서 풀면된다.

입력이 아래와 같다면

5 3 7 8 6 2 9 4

5가 마지막이 되는 경우 부분 증가수열을 만든다. 그러면 5 하나만 들어가는 수열이 나오게 되므로

최대길이는 1이다. 

그 다음 3이 마지막이 되는 경우의 부분증가수열을 만든다. 3이 수열의 마지막이 되는 경우 5 3은 증가수열이 아니므로 3 하나만 들어가는 수열이 나오게 된다. 따라서 최대길이는 1이다.

7이 마지막이 되는 경우의 부분증가수열은 5 7 / 3 7 이다. 따라서 최대길이는 2이다.

8이 마지막이 되는 경우의 부분증가수열은 5 7 8 / 3 7 8 이다. 최대길이는 3이다.

6이 마지막이 되는 경우의 부분증가수열은 5 6 / 3 6 이다. 최대길이는 2이다.

2가 마지막이 되는 경우의 부분증가수열은 2 이다. 최대길이는 1이다.

이런 방식으로 배열의 마지막 숫자까지 부분증가수열의 최대길이를 구한다.

 

여기에서 dp접근법으로 문제를 다시보면 

각각의 숫자가 마지막이 되는 경우에서 최대길이를 구할 때

해당 숫자 전에 있는 숫자가 해당숫자보다 더 작고 최대길이를 가진 경우 그 길이에 1을 더하면 해당 숫자의 최대길이를 구할 수 있다.

이러한 방법으로 마지막 숫자까지 구하면서 최대길이를 출력한다.