[SWEA_3307] 최장 증가 수열(LIS, Longest Increasing Subsequence)

[문제]

주어진 두 수열의 최장 증가 부분 수열(Longest Increasing Subsequence)의 길이를 계산하는 프로그램을 작성하시오.

수열 { A1, A2, ... , AN }의 최장 증가 부분 수열 B는 다음과 같이 정의된다.

{ B1, B2, ... , BK }에서 0≤K≤N, B1 ≤ B2 ≤ ... ≤ BK이고,

AB1 ≤ AB2 ≤ ... ≤ ABK인 최대 K로 구성된 수열이다.

예를 들어, 수열이 { 1, 3, 2, 5, 4, 7 } 이라면, 최장 부분 증가 수열의 길이는 4가 된다.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 수열의 길이 N(1≤N≤1,000)이 주어진다. 

둘째 줄에는 수열의 원소 N개가 공백을 사이에 두고 순서대로 주어진다.

각 수열의 원소는 1 이상 231-1 이하의 자연수이다.

[출력]

각 테스트 케이스마다 ‘#T’(T는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최대 증가 부분 수열의 길이를 출력한다.

[입력]

2

5
1 3 2 5 4 
6
4 2 3 1 5 6

 

 

[출력]

#1 3
#2 4
 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_3370 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int t = 1; t <= T; t++) { // 테스트 케이스
			int N = Integer.parseInt(br.readLine());
			int[] list = new int[N];
			int[] dp = new int[N];

			int max = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				list[i] = Integer.parseInt(st.nextToken());
			}

			dp[0] = 1;

			for (int i = 1; i < N; i++) {
				dp[i] = 1; // 모두 한가지 방법은 있음 (자기자신)
//				System.out.println(Arrays.toString(list));
//				System.out.println(Arrays.toString(dp));
				for (int pre = 0; pre < i; pre++) { // 4 2 3
					if (list[i] > list[pre] && dp[pre] + 1 > dp[i])
						dp[i] = dp[pre] + 1;
				}
				max = Math.max(max, dp[i]); // 지금까지의 max랑 현재까지의 값과 비교
			}
			System.out.println("#" + t + " " + max);
		}
	}
}

https://dheldh77.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EC%88%98%EC%97%B4LIS-Longest-Increasing-Subsequence

[알고리즘] 최장 증가 수열(LIS, Longest Increasing Subsequence)