문제
풀이
•
처음에 그냥 set 에 넣고 그 크기만 재면 될거라고 생각했는데 틀렸다.
◦
사실 아직도 논리가 뭐가 틀렸는지 잘 모르겠다.
•
일반항
◦
현재 index를 앞에있는 값중에
◦
나보다 작으면서 가장 큰값 + 1 을 dp에 대입
구현
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int n;
vector<int> arr;
vector<int> dp;
void pre() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
void input() {
cin >> n;
arr.resize(n);
dp.resize(n, 0);
for(int i = 0; i < n; i++)
cin >> arr[i];
}
int rec(int index) {
if (index == n)
return (dp[index - 1]);
for(int i = 0; i < index; i++)
if (arr[i] < arr[index])
dp[index] = max(dp[index], dp[i]);
dp[index]++;
return (max(rec(index + 1), dp[index]));
}
void solve() {
cout << rec(0) << endl;
}
int main() {
input();
solve();
return (0);
}
C++
복사
