가장 긴 증가하는 부분 수열4

틀린 이유 : 가장 긴 시리즈3을 해결 후 4를 도전 했는데 어려웠다...
1. 처음에는 수열 값도 출력을 하라길래 매순간에 넣어두면 되지 않나 생각 했는데 아니다..

2. upperbound로 이용 해볼까 했는데 실패..

다른 블로그들을 참고 하면서 풀었다

 

풀이 :

점화식 정의 :

dp[a] =b -> a번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 b이다.

vector lis[] -> list[a] = {...} => a번째 값이 가장 긴 증가하는 부분 수열은 벡터 원소들이다.

for (int i = 1; i <= n; ++i) {
		dp[i] = 1;
		lis[i].push_back(a[i]);

		for (int j = 1; j < n; ++j) {
			if (a[i] > a[j]) {
				
				//가장 긴 수열 길이 저장
				if (dp[i] < dp[j] + 1) {
					lis[i].clear();
					lis[i] = lis[j];
					
					//lis[j]까지 원소 넣고 현재 i번째 원소도 넣어야지 lis[i] -> i번째에서 가장 긴 수열원소는 벡터의 원소이다가 성립한다 
					lis[i].push_back(a[i]);
					dp[i] = dp[j] + 1;
				}
			}
		}
		if (answer.size() < lis[i].size()) {
			answer = lis[i];
		}

위와 같이 dp[i] < dp[j] + 1로 갱신 하면서 lis도 변경을 해주는 식이다 

마지막 answer 사이즈와 lis 사이즈를 비교하면서 크기가 크다 -> 길이가 길다 이므로 비교한다