[11053,11722,11054] 가장 긴 X하는 부분 수열, LIS

가장 긴 증가하는 부분 수열 $O(N^{2})$ 풀이

dp[i]는 길이가 i인 경우의 LIS(Longest Increasing Squence)의 길이를 의미합니다. $O(N^{2})$ 알고리즘으로 모든 경우를 다 훑어보는 방법을 사용합니다.

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
long long v[1001];
long long dp[1001];
int n;
priority_queue<int, vector<int>, less<int> > pq;
int main(void) {
	scanf("%d", &n);
	for (int j = 1; j <= n; j++) {
		scanf("%lld", &v[j]);
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (v[j] < v[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
			}
		}
		pq.push(dp[i]);
	}
	printf("%d\n", pq.top());
	return 0;
}

//max_element 사용해보기

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
long long v[1001];
long long dp[1001];
int n;
vector<int > vec;
int main(void) {
	scanf("%d", &n);
	for (int j = 1; j <= n; j++) {
		scanf("%lld", &v[j]);
	}
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = 1; j < i; j++) {
			if (v[j] < v[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
			}
		}
		vec.push_back(dp[i]);
	}
	printf("%d\n", *max_element(vec.begin(), vec.end()));
	return 0;
}

가장 긴 감소하는 부분 수열의 길이

if()에 들어가는 부호만 바꾸면 됩니다.

#include <cstdio>
#include <algorithm>
using namespace std;
long long v[1001];
long long dp[1001];
int n;
int main(void) {
	scanf("%d", &n);
	for (int j = 1; j <= n; j++) {
		scanf("%lld", &v[j]);
	}

	for (int i = 1; i <=n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (v[j] > v[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
			}
		}
	}
	printf("%lld\n", *max_element(dp+1, dp + n + 1));
	return 0;
}

가장 긴 바이토닉 부분 수열 $O(N^{2})$ 풀이

모든 위치에서 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 구한다. 그리고 각 idx에서 이들의 합 중 제일 큰 값을 출력한다.
단 123454321과 같은 경우, 5에서 증가하는 부분 수열의 길이와 감소하는 부분 수열의 길이가 모두 5가 저장되도록 해야한다.

코드

#include <cstdio>

int v[1001];
int asc[1001];
int dsc[1001];
int n;

int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
	}
	for (int i = 1; i <= n; i++) {
		asc[i] = 1;
		for (int j = 1; j < i; j++) {
			if (v[j] < v[i] && asc[j] + 1 > asc[i]) {
				asc[i] = asc[j] + 1;
			}
		}
	}
	for (int i = n; i >=1; i--) {
		dsc[i] = 1;
		for (int j = n; i< j; j--) {
			if (v[j] < v[i] && dsc[j] + 1 > dsc[i]) {
				dsc[i] = dsc[j] + 1;
			}
		}
	}
	int ans = 0;
	for (int k = 1; k <= n; k++) {
		ans = ans < asc[k] + dsc[k] - 1 ? asc[k] + dsc[k] - 1 : ans;
	}
	printf("%d\n", ans);

	return 0;
}