백준
백준 소스코드 [C++] 11722 가장 긴 감소하는 부분 수열
Hani_Levenshtein
2020. 10. 10. 14:59
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} �
www.acmicpc.net
백준 소스코드 [C++] 11722 가장 긴 감소하는 부분 수열
#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] = 1001;
for (int i = 1;i <= n;i++) {
dp[1001] = 1001;
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;
}