개념 링크:
Longest Increasing Subsequence | DP-3 - GeeksforGeeks
We have discussed Overlapping Subproblems and Optimal Substructure properties. Let us discuss Longest Increasing Subsequence (LIS) problem as an example problem that can be solved… Read More »
www.geeksforgeeks.org
문제 링크:
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
// Top Down(Memoization)?
#include <iostream>
#include <algorithm>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int N;
int A[1000], lookup[1000];
int LIS(int i) {
if (!lookup[i]) {
lookup[i] = 1;
f(j, i)
if (A[i] > A[j] && lookup[i] < LIS(j) + 1)
lookup[i] = lookup[j] + 1;
}
return lookup[i];
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
f(i, N) {
cin >> A[i];
LIS(i);
}
cout << *max_element(lookup, lookup + N);
return 0;
}// Bottom Up(Tabulation)
#include <iostream>
#include <algorithm>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int N;
int A[1000], LIS[1000];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
f(i, N) {
cin >> A[i];
LIS[i] = 1;
f(j, i)
if (A[i] > A[j] && LIS[i] < LIS[j] + 1)
LIS[i] = LIS[j] + 1;
}
cout << *max_element(LIS, LIS + N);
return 0;
}