가장 긴 증가하는 부분 수열 11053 (백준으로 C++ 공부하기 35일차)

문제

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

생각

 

코드

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

int main() {
	int n;
	int dp[1000];
	int arr[1000];
	int sum = 0;
	cin >> n;

	for (int i = 0; i < n; i++) cin >> arr[i];

	for (int i = 0; i < n; i++) { //현재 위치
        //자기 자신만으로도 1
		dp[i] = 1;

		for (int j = 0; j < i; j++) { //검사위치
			if (arr[i] > arr[j]) //현재위치보다 뒤쪽에서 자신보다 작을 게 있으면 + 1
                dp[i] = max(dp[i], dp[j] + 1);
		}
		sum = max(sum, dp[i]);
	}
	
	cout << sum << endl;
}