문제

코드

231013 수정

import java.util.Scanner;

public class q11053 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] numbers = new int[N];
        int[] memo = new int[N];
        for(int i=0; i<numbers.length; i++) numbers[i] = sc.nextInt();

        int result = memo[0] = 1;
        for(int i=1; i<numbers.length; i++) {
            int max = 0; // 이전 자기보다 작은 수 중 memo 값이 가장 큰 수
            for(int j=0; j<i; j++) {
                if(numbers[j] < numbers[i] && max < memo[j]) max = memo[j];
            }

            // 조건에 맞는 수가 없을 경우 memo에 1 저장
            if(max == 0) memo[i] = 1;
            // 조건에 맞는 수가 있을 경우 ++하여 저장
            else memo[i] = ++max;

            // 최댓값 저장
            if(memo[i] > result) result = memo[i];
        }
        System.out.print(result);
    }
}

import java.util.Scanner;

public class q11053_3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] arr = new int[N+1];
        arr[0] = 0;
        for(int i=1; i<arr.length; i++) arr[i] = sc.nextInt();

        int[] memo = new int[1001];
        memo[0] = 0;

        for(int i=1; i<arr.length; i++) {
            if(arr[i-1] != arr[i]) {
                int max = 0;
                for(int j=arr[i]-1; j>0; j--) {
                    if(memo[j] > max) max = memo[j];
                }
                memo[arr[i]] = Math.max(memo[arr[i]], max+1);
            }
        }

        int max = 0;
        for(int num : arr) {
            if(max < memo[num]) max = memo[num];
        }
        System.out.println(max);
    }
}