글 읽기 - 이런식으로 접근해도 맞는건가요?

tnswoekd 7년 전 0

역순으로 입력받고 가장 긴 증가하는 부분수열의 개수를 출력하는 형식으로 풀었습니다.

자꾸 틀리는데 접근방법 자체가 잘못된걸까요?

#include <iostream>
#include <algorithm>
#define MAX_N 1001

using namespace std;

int arr[MAX_N];
int dp[MAX_N];
int n;

int main() {
	cin >> n;
	for (int i = n - 1; i >= 0; i--) {
		cin >> arr[i];
	}

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

	int mx;
	for (int i = 0; i < n; i++) mx = max(mx, dp[i]);
	cout << mx + 1;

	return 0;
}