최대 부분 증가 수열(LIS)
문제
설명
N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어
길이가 5인 최대 부분 증가수열을 만들 수 있다.
입력
첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.
출력
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
예시 입력 1
8
5 3 7 8 6 2 9 4
예시 출력 1
4
해결방법
- 증가 수열을 체크할 때는 보통 순서가 보장 되므로 신경 쓸 필요 없고, 다이나믹 배열의 원소에 어떤 값을 넣을 것 인가를 정해야 한다.
- 숫자가 고정 이므로, 최대 증가 수열을 뽑기 위해서는 해당 배열의 원소를 마지막으로 하는 최대 길이를 각각 체크하여 저장하고 비교해야 한다.
코드
import java.util.*;
class Main {
static int[] dy;
public int solution(int[] arr) {
int answer = 0;
// 배열의 길이 만큼 다이나믹 배열 생성
// 다이나믹 배열에는 배열 인덱스의 원소를 마지막으로 하는 최대증가 수열의 길이를 저장한다.
dy = new int[arr.length];
dy[0] = 1;
// 배열의 길이만큼 반복한다. (최대 증가 수열에서는 순서가 보장된다.)
for (int i = 1; i < arr.length; i++) {
// 최대값을 정답으로 체크해야되니 선언.
int max = 0;
// 다이나믹 배열체크
// 현재 배열 원소의 앞에 것들 전부 체크하는 로직
for (int j = i - 1; j >= 0; j--) {
// 현재 배열 원소보다 작은 것 + 그 작은 값의 길이가 최대값보다 큰 경우 교체.
if (arr[j] < arr[i] && dy[j] > max) max = dy[j];
}
// 앞에꺼 전부 체크 했으면 최대값 + 1 을 하여 정의.
// 왜 +1 ? -> i번째 숫자가 j번쨰 바로 뒤에 추가되므로.
dy[i] = max + 1;
// 최대값이랑 현재 배열 원소를 마지막으로 하는 최대 증가 수열 길이를 비교하여 교체.
answer = Math.max(answer, dy[i]);
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = kb.nextInt();
}
System.out.print(T.solution(arr));
}
}
