[JAVA] 최장 증가 수열 LIS (Longest Increasing Subsequence)
최장증가수열(LIS)란 ? 어떤 임의의 수열이 주어졌을때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장증가수열이라고 한다. 동적계획법으로 풀 수 있는 알고리즘 중 하나 예시 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {**10**, **20**, 10, **30**, 20, **50**} 이고, 길이는 4이다. 방법 수열이 들어있는 배열 : array 인덱스마다 각 증가 수열의 길이 배열 : dp Step 1. 2중포문 j : i를 기준으로 인덱스 0에서부터 i-1까지 체크한다. Step ..
