처음에 접근할 때는
for i = 0 to n-1
for j = 0 to i
DP(i)가 가장 큰 값이라면 res++;이런 방식으로 접근을 했다.
근데 해결이 안 되고 어떻게 해야할지 몰라서 구글링 해보았음
우선 메모제이션 기법 사용
dp[n]이 n번째 수로 끝나는 부분수열 중 가장 긴 것의 길이를 의미함
n번째 수로 끝나는 부분 수열에서는 n번째 수가 마지막이기 때문에 n-1까지만 살펴보면 됨.
감소하는 부분 수열을 유지하기 위해서는 arr[n]로 끝나는 부분 수열에서 arr[n]앞에 올 수 있는 숫자는 반드시 arr[n]보다 커야함.
즉 [0]~[n-1] 중에서 arr[n]보다 큰 숫자만 검사하면 됨!
if arr[j] > arr[i]
dp[i] = max(dp[j]+1, dp[i]);
이전 값(j)가 현재 인덱스 값(i)보다 크다면 dp값을 갱신해줌
최장 길이가 되기 위해 이전 값에 이미 저장된 가장 긴 부분수열 길이 +1의 값과 현재 인덱스의 값 중에 큰 값을 선택하면 됨
(부분 수열을 완성했을 때 최장길이가 되기 위해선 당연히 dp[n이전의 인덱스(j) +1]은 dp[n]의 현재 값보다 더 커야 함.
제출 코드
public class Main {
static int inputs[];
static int DP[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
inputs = new int[n+1];
DP = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
int k = 0;
while (st.hasMoreTokens()) {
inputs[k++] = Integer.parseInt(st.nextToken());
}
DP[0] = 1;
for (int i = 1; i < n; i++) {
DP[i] = 1;
for (int j = 0; j < i; j++) {
if (inputs[j] > inputs[i]) {
DP[i] = Math.max(DP[j] + 1, DP[i]);
}
}
}
OptionalInt opI = Arrays.stream(DP).max();
System.out.println(opI.getAsInt());
}
}