알고리즘 공부방

우선, $O(N^2)$ DP 풀이부터 살펴 보자. $dp[i]$ = $0$ ~ $i$ 구간에서 $i$를 끝으로 하는 lis의 최대 길이 $dp[i]$ = $0$ ~ $i-1$ 의 $j$ 에 대하여 $arr[i]>arr[j]$를 만족하고, $dp[j]+1$의 최대값을 만족한다. 여기서는 구현할 때 처음에 NEGINF, 끝에 INF 를 추가해서 구현하였고, 동시에 전 단계로의 선택 과정을 담아 복원까지 했다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int MAXN = 1000; const int INF = numeric_limits::max(); const int NEGINF = ..