[JAVA] SWEA 3307 - 최장 증가 부분 수열
Solution
- dp[i] : i 값을 포함하는 최장 증가 부분 수열의 길이
- 각 배열 값들을 보면서 이전까지 이어져온 최장 증가 부분 수열(A)의 마지막 값(=min)보다 크거나 같으면 해당 값을 최장 증가 부분 수열에 추가
- 만약에 마지막 값보다 작다면 해당 인덱스의 앞부터 보면서 해당 값보다 작거나 같고 dp 값이 가장 큰 최장 증가 부분 수열(B)에 추가
- 현재 최장 증가 부분 수열(A)보다 새롭게 값을 추가한 최장 증가 부분 수열(B)의 길이가 더 길어진다면, 최장 증가 부분 수열을 B로 교체
Code
import java.util.*;
class Solution
{
public static void main(String args[]) throws Exception
{
Scanner sc = new Scanner(System.in);
StringBuffer sb = new StringBuffer();
int T = Integer.parseInt(sc.nextLine());
for(int tc=1; tc<=T; tc++){
sb.append("#").append(tc).append(" ");
int N = sc.nextInt();
int array[] = new int[N];
for(int i=0; i<N; i++){
array[i] = sc.nextInt();
}
int dp[] = new int[N];
int min = 0;
int len = 0;
for(int i=0; i<N; i++){
if(array[i] >= min){
len++;
min = array[i];
dp[i] = len;
}else {
int index = 0;
int max = 0;
for (int j = i - 1; j >= 0; j--) {
if (array[j] <= array[i]) {
if (max < dp[j]) {
max = dp[j];
index = j;
}
}
}
dp[i] = max + 1;
if(len < dp[i]){
len = dp[i];
min = array[i];
}
}
}
sb.append(len).append("\n");
}
System.out.println(sb);
}
}
Author And Source
이 문제에 관하여([JAVA] SWEA 3307 - 최장 증가 부분 수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gkdud583/JAVA-SWEA-3307-최장-증가-부분-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)