[백준] 11053. 가장 긴 증가하는 부분 수열

❓ 문제 ❓
가장 긴 증가하는 부분 수열

💯 문제 풀이💯
기본 길이가 1이므로 모든 dp배열을 1로 초기화 한다음 arr[i] > arr[j]일때 점화식 dp[i] = max(dp[i], dp[j] + 1)을 통해 i 배열이 j 배열보다 크다면 dp값을 1증가 시키고 dp배열에서 가장 큰 값을 출력함으로써 가장 긴 길이를 출력한다.

#include <iostream>
#include <algorithm>
using namespace std;
int arr[1001], dp[1001];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = 1;
	int answer = 0;

	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[i] <= dp[j])
				dp[i] = dp[j] + 1;
		}
		answer = max(answer, dp[i]);
	}
	cout << answer;
}