136. 11053(가장 긴 증가하는 부분 수열)

import java.util.*;
import java.io.*;

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		int[] arrDp = new int[n];
		String[] tmp = br.readLine().split(" ");

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(tmp[i]);
			arrDp[i] = 1;
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i] > arr[j]) {
					arrDp[i] = Math.max(arrDp[i], arrDp[j]+1);
				}
			}
		}
		
		Arrays.sort(arrDp);
		
		System.out.println(arrDp[arrDp.length-1]);
	}
}

문제요약

증가하는 수열이 가장 긴 부분은?

설명

코드는 크게 어렵지 않을 것이다.

7
1 4 5 2 3 4 5

로 보자.

값을 하나하나 다 비교해서 수열이 가장 긴 부분에 대해서 가져가면 된다.

 

먼저 각 인덱스는 1의 수열을 가질 수 있어 1로 초기화 해주었다.

for (int i = 0; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if(arr[i] > arr[j]) {
					arrDp[i] = Math.max(arrDp[i], arrDp[j]+1);
				}
			}
		}

arr를 0부터 해당 인덱스(i) 전까지 비교한다.

만약 해당 인덱스가(i) 가 비교 도중 부분 인덱스(j) 보다 크다면 Dp에 저장된 길이를 비교하는데, 자기자신이 가지고 있ㄴ는 길이, 부분 인덱스(j)에서 +1한 길이 중 더 큰 것을 저장한다.

 

Arrays.sort(arrDp);
		
System.out.println(arrDp[arrDp.length-1]);

마지막에 가장 큰 부분을 출력해주면 답을 맞출 수 있다.