-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy path_11054.java
More file actions
80 lines (57 loc) ยท 1.78 KB
/
_11054.java
File metadata and controls
80 lines (57 loc) ยท 1.78 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
package backjoon;
// https://www.acmicpc.net/problem/11054
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class _11054 {
static int N;
static int[] seq;
static int[] r_dp;
static int[] l_dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine()," ");
r_dp = new int[N]; // LIS
l_dp = new int[N]; // LDS
seq = new int[N];
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
LIS();
LDS();
int max = 0;
for(int i = 0; i < N; i++) {
if(max < r_dp[i] + l_dp[i]) {
max = r_dp[i] + l_dp[i];
}
}
System.out.println(max - 1);
}
static void LIS() {
for(int i = 0; i < N; i++) {
r_dp[i] = 1;
// 0 ~ i ์ด์ ์์๋ค ํ์
for(int j = 0; j < i; j++) {
// j๋ฒ์งธ ์์๊ฐ i๋ฒ์งธ ์์๋ณด๋ค ์์ผ๋ฉด์ i๋ฒ์งธ dp๊ฐ j๋ฒ์งธ dp+1 ๊ฐ๋ณด๋ค ์์๊ฒฝ์ฐ
if(seq[j] < seq[i] && r_dp[i] < r_dp[j] + 1) {
r_dp[i] = r_dp[j] + 1; // j๋ฒ์งธ ์์์ +1 ๊ฐ์ด i๋ฒ์งธ dp๊ฐ ๋๋ค.
}
}
}
}
static void LDS() {
// ๋ค์์๋ถํฐ ์์
for (int i = N - 1; i >= 0; i--) {
l_dp[i] = 1;
// ๋งจ ๋ค์์ i ์ด์ ์์๋ค์ ํ์
for (int j = N - 1; j > i; j--) {
// i๋ฒ์งธ ์์๊ฐ j๋ฒ์งธ ์์๋ณด๋ค ํฌ๋ฉด์ i๋ฒ์งธ dp๊ฐ j๋ฒ์งธ dp+1 ๊ฐ๋ณด๋ค ์์๊ฒฝ์ฐ
if (seq[j] < seq[i] && l_dp[i] < l_dp[j] + 1) {
l_dp[i] = l_dp[j] + 1; // j๋ฒ์จฐ ์์์ +1์ด i๋ฒ์จฐ dp๊ฐ์ด ๋จ
}
}
}
}
}