[BOJ/C++] 11053 가장 긴 증가하는 부분 수열

문제

https://www.acmicpc.net/problem/11053

풀이

🥑가장 긴 증가하는 부분 수열(LIS) 구하는 문제

ex) v[1, 2, 1, 3, 4, 2]

v[0] = 1
LIS : 1

v[1] = 2
LIS : 2 // (1-2)

v[2] = 1
LIS : 1

v[3] = 3
LIS : 3 // (1-2-3), (2-3), (1-3)

=> LIS : 이전에 나온 숫자들 중에서, 현재 값보다 작은 값 중에 가지고 있는 부분 수열의 길이 중 가장 긴 부분 수열의 길이에 +1을 한 값

코드

#include <iostream>
#include <vector>

using namespace std;

int dp[1001];

int main() {
	int N;
	vector<int> v;
	int ans = 0;

	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;

		cin >> tmp;
		v.push_back(tmp);
	}

	for (int i = 0; i < N; i++) {
		dp[i] = 1;

		for (int j = 0; j < i; j++) {
			if (v[i] > v[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}

	cout << ans;

	return 0;
}