10211번: Maximum Subarray
크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있
www.acmicpc.net
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
위의 문제와 같은문제이지만 N의 범위가 적게 들어옵니다.
저는 dp와 세그먼트 트리 두가지 방법으로 해결하였습니다.
이 문제는 당연히 dp로 해결한 것이 속도가 빠르기 때문에 dp로 접근하시면 됩니다.
세그먼트 트리는 그냥 해본거에요..
근데 이문제는 그냥 브루트포스로 모든경우를 다구해도 풀립니다.. 밑에 소스첨부합니다
dp의 점화식은 이전 인덱스까지 더한 dp값에 현재 자신의 값을 더한것과 자신의 값 중 큰 값이되어
dp[i] = max(dp[i - 1] + list[i], list[i]) 가 되겠습니다.
[dp]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int list[], dp[];
static int N;
static void func() {
int ans = Integer.MIN_VALUE;
for (int i = 1; i <= N; i++) {
dp[i] = Math.max(dp[i - 1] + list[i], list[i]);
ans = Math.max(ans, dp[i]);
}
sb.append(ans).append("\n");
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N + 1];
dp = new int[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
}
System.out.println(sb.toString());
}
}
|
cs |
세그먼트 트리 방법으로는 입력으로 list를 받으면
init함수로 각 구간의 합을 미리 구해놓습니다.
이중 for문으로 (i, i ~ N)까지 구간 합의 최대를 구해주시면 됩니다.
[세그먼트 트리]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int tree[] = new int[4004];
static int list[] = new int[1001];
static int N;
static int init(int node, int s, int e) {
if (s == e)
return tree[node] = list[s];
int m = (s + e) / 2;
return tree[node] = init(node * 2, s, m) + init(node * 2 + 1, m + 1, e);
}
static int query(int node, int s, int e, int l, int r) {
if (s > r || l > e)
return 0;
if (l <= s && e <= r)
return tree[node];
int m = (s + e) / 2;
return query(node * 2, s, m, l, r) + query(node * 2 + 1, m + 1, e, l, r);
}
static void func() {
int ans = Integer.MIN_VALUE;
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
ans = Math.max(ans, query(1, 1, N, i, j));
}
}
sb.append(ans).append("\n");
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
init(1, 1, N);
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
}
System.out.println(sb.toString());
}
}
|
cs |
[브루트포스]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static int list[];
static int N;
static void func() {
int ans = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += list[k];
}
ans = Math.max(ans, sum);
}
}
sb.append(ans).append("\n");
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
list[i] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
int tc = Integer.parseInt(st.nextToken());
while (tc-- > 0) {
input();
func();
}
System.out.println(sb.toString());
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1915 가장 큰 정사각형 (0) | 2021.02.20 |
|---|---|
| boj 1912 연속합 (0) | 2021.02.18 |
| boj 10826 피보나치 수 4 (0) | 2021.02.08 |
| boj 5569 출근 경로 (0) | 2021.02.06 |
| boj 1010 다리 놓기 (0) | 2021.02.05 |