Java : 최대 부분 증가 수열(LIS)

문제

풀이

LIS 설명이 잘 되어 있다.

DP 풀이 방식 : 시간 복잡도 O(N²)

• 인풋 배열의 크기 만큼 빈 배열(dy)을 만든다.
• 인풋 배열 i 를 순회하며 매 차례 이전 원소들 j를 검사하면서 현재 원소가 몇 번
  째로 큰 원소인지 판단한다.

// dy 배열 : 최장 길이를 체크해둘 배열
// max : 최대 길이를 담아둘 변수, 중복해서 카운트 되는 것 방지 역할
//
// 처음 값은 무조건 길이가 1이므로 초기화 
dy[0] = 1;
for (int i = 1; i < n; i++) {
	// i를 돌릴 때마다 j의 최대 값은 초기화 시켜준다.
	int max = 0;
    	// i의 이전 원소부터 처음까지 확인한다.
	for (int j = i - 1; j >= 0; j--) {
    		// 현재 원소가 이전 원소보다 값이 크고
            	// dy[j]가 max 보다 크면 max 값 갱신
		if (arr[i] > arr[j] && dy[j] > max) max = dy[j];
	}
	// 현재까지 max 값은 최대 증가 수열의 값을 나타내므로 1 증가 시켜준다
	dy[i] = max + 1;
    	// 최대 길이 갱신
	if (dy[i] > ans) ans = dy[i];
}

잡담

전체코드

DP 풀이 O(N²)

package inflearn;

import java.util.Scanner;

public class I1003 {
	static int[] dy;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		dy = new int[n];
		int[] arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}

		System.out.println(solution(n, arr));
	}

	static int solution(int n, int[] arr) {
		int ans = 0;
		dy[0] = 1;

		for (int i = 1; i < n; i++) {
			int max = 0;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[i] > arr[j] && dy[j] > max) max = dy[j];
			}
			dy[i] = max + 1;
			if (dy[i] > ans) ans = dy[i];
		}
		return ans;
	}
}