[C++] 백준 11053 : 가장 긴 증가하는 부분 수열

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

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

백준 11053번 가장 긴 증가하는 부분 수열을 풀어봤습니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int n;
int sequence[1000];
int len[1000];

void dp(int N) {
	for (int i = 0; i < N; i++) {
		len[i] = 1;
		for (int j = 0; j < i; j++) {
			if (sequence[i] > sequence[j]) {
				len[i] = max(len[i], len[j] + 1);
			}
		}
	}
}

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

	dp(n);

	int max = 0;
	for (int i = 0; i < n; i++) {
		if (max < len[i])
			max = len[i];
	}

	cout << max;

	return 0;
}