백준 소스코드 [C++] 11053 가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

백준 소스코드 [C++] 11053 가장 긴 증가하는 부분 수열

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
typedef long long ll;
using namespace std;
int arr[1001], dp[1001];
int search(int n) {
	int res = 0;
	dp[1] = arr[1];
	dp[0] = -1;
	for (int i = 1;i <= n;i++) {
		for (int j = res;0 <= j;j--) {
			if (dp[j] < arr[i]) {
				dp[j + 1] = arr[i];
				if (j == res ) res++;
				break;
			}
		}

	}
	return res;
}
int main() {
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> arr[i];
	cout << search(n);

	return 0;
}