(cpp) Baekjoon 11053번 문제 ‘가장 긴 증가하는 부분 수열’ - 다이나믹 프로그래밍

02 Oct 2022 on Programming Languages

Baekjoon 11053번 문제 ‘가장 긴 증가하는 부분 수열’ - 다이나믹 프로그래밍

---

문제

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<vector>
#include<iostream>
using namespace std;

int n, a;
vector<int> alist;
vector<int> v;

int main() {
	cin >> n;
	int ret = n;
	while (ret--) {
		cin >> a;
		alist.push_back(a);
	}

	v.push_back(alist[0]);

	for (int i = 1; i < n; i++) {
		for (int j = v.size() - 1; j >= 0; j--) {
			if (v[j] < alist[i]) {
				if (j == v.size() - 1) { v.push_back(alist[i]); }
				else v[j + 1] = alist[i];
				break;
			}
			if (j == 0) { v[0] = alist[i]; }
		}
	}

	cout << v.size();
	return 0;

}