03. 최대 부분 증가수열

 

설명

부분증가수열의 최대 길이를 출력한다.

 

 

 

예시

8

5 3 7 8 6 2 9 4

 

4

 

 

 

 

풀이

j=i-1부터 0까지 감소하면서

 

만약 나보다 arr[j]가 작고&& len[j]가 max보다 크다면 max값을 바꾸어준다.

 

그리고 그 max+1한값이 내가된다.

 

그리고 len배열을 돌면서 제일 큰 값이 answer가 된다.

 

import java.util.*;



class Main {
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		
		int n= sc.nextInt();
		
		int [] arr = new int[n];
		int [] len = new int[n];
		for(int i=0; i<n; i++) {
			arr[i]=sc.nextInt();
		}
		int answer=0;
		
		for(int i=0; i<n ;i++) {
			int max=0;
			for(int j=i-1; j>=0; j--) {
				if(arr[j]<arr[i] &&len[j]>max) {
					max=len[j];
				}
			}
			len[i]=max+1;
			answer=Math.max(answer, len[i]);
		}
		

		System.out.println(answer);
		

	}

	
}