ex) 3,2,6 ->
3 32 x 326 x
2 36
6 26
->x 표시는 줄어들어서 안됨
따라서 이 예제의 답은 2 (가장 긴 길이가 2)
-> 부분집합(넣을까 말까)으로 풀어내면 7개의 예시 답을 얻을 수 있다.
-> 점진적인 성질을 갖추면서 길이가 가장 긴 수열을 찾자 !!
** LIS (Longest Increasing Subsequence)
부분 수열의 길이가 긴 것부터 조사하는 것이 유리
시간 복잡도 = O(2n) (2의 n승) -> n이 점진적으로 커지면 무한대가 되기 때문에 풀 수 없다.
D[n] : n원소를 끝에 세웠을 때 최장 길이