DP - LIS(최장 증가 수열) 및 0-1 Knapsack 개념 (JAVA)

최장 증가 부분 수열(LIS) 최장 증가 부분 수열이란? 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로, 순서를 유지한 채 몇 개의 숫자들을 뽑아서 부분 수열을 만들 수 있다. 이렇게 만들 수 있는 부분 수열 중 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어, [6, 2, 1, 4, 3, 5]라는 수열이 있다면마지막 원소 5를 붙일 거라면, 5보다 앞에 있고, 5보다 작은 수로 끝나는 가장 긴 부분 수열에 붙이는 것이 좋다. [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이다. (여러 개 일 수 있다. ) DP를 활용하여 O(N²)으로 구해보기 배열의 숫자를 하나씩 살펴..