11053 백준 가장 긴 증가하는 부분수열

package solution;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int arr[] = new int [1001];
    int arr2[] = new int [1001];
    int cnt = 0;
    int max_count = 0;
    int testcase = sc.nextInt();
    for(int i = 0; i < testcase; i++){
        arr[i] = sc.nextInt();
    }
    for(int i = 0; i < testcase; i++){
        cnt = 0;
        for(int j = 0; j < i; j++){
            if(arr[j] < arr[i]){
                cnt = Math.max(arr2[j], cnt);
            }
        }
        arr2[i] = cnt + 1;
        if(max_count < arr2[i])
            max_count = arr2[i];
    }
    System.out.println(max_count);
    }
}
 

그냥 자기자신보다 낮은 수를 저장하는 배열을 하나 만들어서 2중포문을 통해 탐색하도록 구현하였다.

만약 자기자신 보다 작은 수라면 그 수가 가진 자신보다 작은 수를 뽑아서 그 중 최대값에 +1 하도록 

설정하였다.

 

<여담>

배열을 하나 만들어서 탐색돌려 자기보다 클때 index를 넣어주고 자기보다 작을때 해당 크기가 들어가는

적절한 위치에 넣어 줄 수 있도록 index를 감소시키면서 배열을 최신화 시켜주면서 그 배열탐색을 하도록하면 주어진

testcase 만큼 돌리지않아도 될 것같다. 즉 계산을 줄일 수 있을 것 같다.