문제
N개의 정수로 이루어진 수열이 주어질 때, 이 수열에서 연속적으로 증가하거나(같아도 됨) 연속적으로 감소하는(같아도 됨) 부분 수열의 최대 길이를 구한다.
입력
첫째 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 0 이상 2,147,483,647 이하이다.
출력
첫째 줄에 연속적으로 증가하거나 감소하는 부분 수열의 최대 길이를 출력한다.
예제
입력
5
1 2 2 3 2출력
4풀이
핵심 아이디어: DP 배열을 두 행으로 나누어, dp[1][i]는 i번째 원소에서 끝나는 비감소 부분 수열의 최대 길이, dp[2][i]는 비증가 부분 수열의 최대 길이를 저장한다.
- 배열
dp[3][n+1]을 선언한다.dp[0]은 원소 값,dp[1]은 비감소(증가) 방향,dp[2]는 비증가(감소) 방향 길이이다. - 첫 번째 원소를 초기화한다:
dp[1][1] = 1,dp[2][1] = 1. i = 2부터n까지 순회하면서:dp[0][i] >= dp[0][i-1]이면dp[1][i] = dp[1][i-1] + 1, 아니면dp[1][i] = 1dp[0][i] <= dp[0][i-1]이면dp[2][i] = dp[2][i-1] + 1, 아니면dp[2][i] = 1- 매 단계에서 두 방향의 최댓값을
max에 갱신한다.
- 최종
max를 출력한다.
인접한 두 원소 비교만으로 O(N) 시간에 처리할 수 있다. 시간 복잡도는 O(N)이며, 복잡한 DP 점화식 없이 단순 선형 탐색으로 해결된다.
코드
import java.util.*;
import java.io.*;
public class Day359BOJ2491수열DP {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] dp = new int[3][n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
dp[0][1] = Integer.parseInt(st.nextToken());
dp[1][1] = 1;
dp[2][1] = 1;
int max = 1;
for (int i = 2; i <= n; i++) {
dp[0][i] = Integer.parseInt(st.nextToken());
if (dp[0][i] >= dp[0][i - 1]) {
dp[1][i] = dp[1][i - 1] + 1;
} else {
dp[1][i] = 1;
}
if (dp[0][i] <= dp[0][i - 1]) {
dp[2][i] = dp[2][i - 1] + 1;
} else {
dp[2][i] = 1;
}
max = Math.max(max, Math.max(dp[1][i], dp[2][i]));
}
System.out.print(max);
}
}복잡도
- 시간: O(N) — 배열을 한 번 순회하며 인접 비교만 수행
- 공간: O(N) — dp 배열 저장