11053번
문제
- 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
문제 해결 순서
- 전형적인 DP 문제. 무엇을 메모이제이션 할 건 지, 어떤 규칙이 있는지 확인하는 것이 키 포인트.
- i번째는 그 이전 (0 ~ i-1)까지의 메모값 중 가장 큰 값 + 1이 된다.
- 처음엔 자꾸 바로 이전 값에서 규칙을 찾으려다 보니 안 찾아짐. (0 ~ i-1)까지 범위를 늘리는 것에 두려워하지 말것.
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int arr[] = new int[n];
int memo[] = new int[n];
int answer = 0;
// 배열 값 입력
for (int i = 0; i < n; i++){
arr[i] = scan.nextInt();
}
for (int i = 0; i < n; i++){
memo[i] = 1;
for (int j = i - 1; j >= 0; j--){
if (arr[j] < arr[i] && memo[i] <= memo[j]){
memo[i] = memo[j] + 1;
}
}
}
for (int i = 0; i < n; i++){
answer = Math.max(answer, memo[i]);
}
System.out.println(answer);
}
}