[백준] 11053번 가장 긴 증가하는 부분 수열 C++ 문제풀이

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

11053번: 가장 긴 증가하는 부분 수열

문제 풀이

DP 문제의 특성을 이용해 한 번의 반복문으로 풀려고 했는데 잘 풀리지 않았다.

이중 반복문을 이용해 최장 증가하는 부분 수열 값을 구했다.

소스 코드

#include <iostream>
using namespace std;

int num[1001] = { 0 };
int cnt[1001] = { 0 };

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num[i];
	}

	for (int i = 0; i < n; i++) {
		cnt[i] = 1;
		for(int j = 0; j < i; j++) {
			if (num[i] > num[j])
				cnt[i] = max(cnt[i], cnt[j] + 1);
		}
	}
	int max_num = 1;
	for (int i = 0; i < n; i++) {
		max_num = max(max_num, cnt[i]);
	}
	cout << max_num << '\n';
}