11053번 '가장 긴 증가하는 부분 수열'

import java.io.*;

class Main {

static int d[];

public static void main(String[] args) throws IOException {

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

int size = Integer.parseInt(in.readLine());

d = new int[size];

String[] input = in.readLine().split(" ");

int[] sequence = new int[size];

for(int i=0; i<size; ++i) {

sequence[i] = Integer.parseInt(input[i]);

}

for(int i=0; i<size; ++i) {

d[i] = 1;

for(int j=0; j<i; ++j) {

if(sequence[j] < sequence[i] && d[i] < d[j] + 1) {

d[i] = d[j] + 1;

}

}

}

int result = 0;

for(int i=0; i<size; ++i) {

if(result < d[i])

result = d[i];

}

System.out.println(result);

}

}

입력받는 건 이제 스캐너를 안써도 될 것 같다.

Memoization 하는 것은 입력된 수열의 각 인덱스가 수열의 마지막일 때 수열을 이루는 원소의 최대 개수다.

증가하는 부분 수열이므로 이전의 요소가 다음의 요소보다 작아야 한다.

해당 Memoization 부분에는 이전의 최대 Memoization에 1을 더해준다.

어렵다...