N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라.
예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어
길이가 5인 최대 부분 증가수열을 만들 수 있다.
첫째 줄은 입력되는 데이터의 수 N(3≤N≤1,000, 자연수)를 의미하고,
둘째 줄은 N개의 입력데이터들이 주어진다.
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
8
5 3 7 8 6 2 9 4
4
2 3 7 5
의 가장 긴 부분 수열을 구하기 위해서는 앞에서부터 순서대로 2
, 2 3
, 2 3 7
, 2 3 5
이런 식으로 탐색해 나가는데 이 과정에서 2 3
처럼 특정 숫자들이 반복되게 된다 -> DP로 점화식을 만들어서 풀어보자!import java.util.Scanner;
public class MaxPartialIncreaseSeq {
static int[] arr;
public int getMaxLength(int N) {
int[] dp = new int[N];
dp[0] = 1;
int maxLength = 0;
for (int i = 1; i < N; i++) {
int max = 0;
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i] && max < dp[j])
max = dp[j];
}
dp[i] = max + 1;
maxLength = Math.max(dp[i], maxLength);
}
return maxLength;
}
public static void main(String[] args) {
MaxPartialIncreaseSeq T = new MaxPartialIncreaseSeq();
Scanner kb = new Scanner(System.in);
int N = kb.nextInt();
arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = kb.nextInt();
}
System.out.println(T.getMaxLength(N));
kb.close();
}
}