<Baekjoon>#14002가장 긴 증가하는 부분 수열4 (Longest increasing subsequence 4) c++

바로 앞에서 풀었던 문제가 부분 수열의 길이만 출력하는 거라면, 이번에는 가장 긴 증가하는 부분수열도 출력해야 한다.

dp의 값이 가장 큰 A의 값부터 시작해서 하나씩 작아지게 역순으로 B에 push_back 한다.
(처음에 dp의 값이 가장 작은 A값부터 B에 push를 했다가 한참을 헤맸다..)
dp[5]=4 A[5]=50의 값을 B에 push
dp[3]=3 A[3]=30의 값을 B에 push
dp[1]=2 A[1]=20의 값을 B에 push
dp[0]=1 A[0]=10의 값을 B에 push

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

const int MAX = 1001;

void lis(const vector<int>& A, int n) {
	vector<int>B;
	int dp[MAX];
	dp[0] = 1;
	int maxLen = 1;

	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j] && dp[i] < dp[j] + 1)
				dp[i] = dp[j] + 1;

			maxLen = max(maxLen, dp[i]);
		}
	}

	int k = maxLen;
	for (int i = n - 1; i >= 0; i--) {
		if (k == 0)
			break;

		if (dp[i] == k) {
			B.push_back(A[i]);
			k--;
		}
	}

	cout << maxLen << endl;

	while (!B.empty()) {
		cout << B.back() << " ";
		B.pop_back();
	}
}

int main() {
	int k;
	cin >> k;

	vector<int>A(k);
	for (int i = 0; i < k; i++)
		cin >> A[i];
	lis(A, k);

	return 0;
}