백준 알고리즘 21단계 이분 탐색 - 가장 긴 증가하는 부분 수열2 (12015번) Java

이번에 풀어볼 문제는 가장 긴 증가하는 부분 수열2이다.

해당 문제 링크는 아래에서 확인할 수 있다.

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

 

1. 문제 확인

 

 

2. 문제 풀이

import java.util.*;
public class Main{
 
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max=0;
        int[] a = new int[n+1];
        int[] b = new int[n+1];
 
        for(int i=0; i<n; i++){
            b[i]=sc.nextInt();
            a[i]=1;
        }
    
        for(int i=0; i<n ; i++){
            for(int j=0 ; j<=i ; j++){
                if(b[j]<b[i] && a[j]>=a[i]){
                    a[i]=a[j]+1;
                }
            }
        }
        
        for(int i=0; i<n ; i++){
            if(a[i]>max)
                max=a[i];
        }
 
        System.out.println( max );
        
    }  
}
 

 

 

3. 결과