최대부분증가 수열

코드

import java.util.Arrays;

public class 최대부분증가수열연습 {
	static int dy[];
	
 	public static void main(String[] args) {
 		//수열
		int[] arr = {5, 3, 7, 8, 6, 2, 9, 4};
		System.out.println(solution(arr));
	}
	static int solution(int[] arr) {
		int answer = 0;
		dy = new int[arr.length];
		dy[0] = 1;
		//수열 순회
		for(int i=1;i<arr.length;i++) {
			//수열 수 저장
			int max = 0;
			//현재 수열 이전 값 중 작은 값있는지 탐색
			for(int j=i;j>=0;j--) {
				//현재 수열보다 작은 값 있으면, 거기에 저장된 수열 횟수 저장
				if(arr[i]>arr[j]) {
					max = Math.max(max, dy[j]);
				}
			}
			//구해진 수열 수에 +1
			dy[i] = max+1;
			//최종적으로 가장 횟수 많은 부분 수열을 구함
			answer = Math.max(answer, dy[i]);
		}
		System.out.println(Arrays.toString(arr));
		System.out.println(Arrays.toString(dy));
		return answer;
	}
}

---

결과

[5, 3, 7, 8, 6, 2, 9, 4]
[1, 1, 2, 3, 2, 1, 4, 2]
4

---

9가 있는 위치를 기준으로 설명

이 기준으로 탐색을 시작

그 값에 +1을 한 것

 

왜 3을 찾아서 +1을 했는가?

8을 기준으로 하면 최대 부분 증가 수열은 3이다.

5-7-8 or -3-7-8  3개

 

9 값이전에서 가장 큰 최대 부분 증가 수열 수는 3이다.

그 값에 +1을 한 것

 

바텀업 방식으로 값을 구한 것이다.

 

문제의 본질을 유지한 상태로 작은 케이스부터 큰 케이스를 탐색하는 방식