최대 부분 증가 수열

N개의 정수로 이루어진 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하라. O(N²) DP로 구현하라.

부분 수열은 원래 수열에서 순서를 유지하며 일부 원소를 제거해 만든다. 증가하는 부분 수열은 선택한 원소가 왼쪽에서 오른쪽으로 갈수록 순증가해야 한다.

예를 들어 [10, 9, 2, 5, 3, 7, 101, 18]에서 LIS는 [2, 5, 7, 101]로 길이 4이다.