[BOJ/JAVA] P11053 가장 긴 증가하는 부분 수열

---

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

---

INPUT & OUTPUT

INPUT

• 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
• 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

예제 입력 1

6
10 20 10 30 20 50

OUTPUT

• 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 출력 1

4

---

STRATEGY

• DP로 해당 문제를 풀 경우, dp[]에 저장되는 값은 부분 배열의 길이

dp[0] = {10} → 길이 1
dp[1] = {10, 20} → 길이 2
dp[2] = {10} → 길이 1
dp[3] = {10, 20, 30} → 길이 3
dp[4] = {10, 20} → 길이 2
dp[5] = {10, 20, 30, 50} → 길이 4

1. 탐색하려는 index에 대해서 이전 위치들을 찾아나가면서 해당 값보다 작을 경우 재귀호출을 통해 탐색해나가기 → TOP DOWN
2. 이중반복문으로 0 ~ N-1 까지 각 원소보다 큰 값들을 카운팅하기 → BOTTOM UP

---

SOLUTION

TOP DOWN

private int LIS(int N) {
	if (dp[N] == 0) {
		dp[N] = 1;
		for (int i = N - 1; i >= 0; i--) {
			if (arr[i] < arr[N]) {
				dp[N] = Math.max(dp[N], LIS(i) + 1);
            }
        }
    }
	return dp[N];
}

BOTTOM UP

for (int i = 0; i < N; i++) {
	dp[i] = 1;
    
	for (int j = 0; j < i; j++) {
    
		if (seq[j] < seq[i] && dp[i] < dp[j] + 1) {
			dp[i] = dp[j] + 1;
		}
	}
}