가장 긴 증가하는 부분 수열

문제 설명

정수 배열 nums가 주어집니다. 가장 긴 순증가 부분 수열(Longest Increasing Subsequence)의 길이를 반환하세요.

부분 수열은 원래 배열의 원소 순서를 유지하면서 일부 원소를 삭제하여 얻을 수 있는 수열입니다.

입력 형식

첫째 줄에 배열의 크기 N이 주어집니다.

둘째 줄에 N개의 정수가 공백으로 구분되어 주어집니다.

출력 형식

가장 긴 증가하는 부분 수열의 길이를 출력합니다.

제약 조건

• 1 ≤ N ≤ 2,500
• -10^4 ≤ nums[i] ≤ 10^4

힌트

O(n²) 동적 프로그래밍 또는 O(n log n) 이진 탐색 방법을 사용할 수 있습니다.