728x90
https://www.acmicpc.net/problem/13398
// 코드
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
|
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
// Please Enter Your Code Here
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] dp1 = new int[N], dp2 = new int[N];
int myMax = arr[0];
// 왼쪽 -> 오른쪽
dp1[0] = arr[0];
for(int i=1; i<N; ++i) {
dp1[i] = Math.max(dp1[i-1] + arr[i], arr[i]);
// 하나도 제거하지 않았을 경우의 최댓값을 구한다.
myMax = Math.max(myMax, dp1[i]);
}
// 오른쪽 -> 왼쪽
dp2[N-1] = arr[N-1];
for(int i=N-2; i>=0; --i)
dp2[i] = Math.max(dp2[i+1] + arr[i], arr[i]);
// 특정값을 지웠다고 가정하고, 그 값의 방향과 왼쪽 방향의 최대 연속합을 더해 최댓값을 찾는다.
for(int i=1; i<N-1; ++i)
myMax = Math.max(myMax, (dp1[i-1] + dp2[i+1]));
bw.write(String.valueOf(myMax));
bw.flush();
bw.close();
br.close();
}
}
|
cs |
반응형
'CS > 알고리즘_문제풀이(자바)' 카테고리의 다른 글
합분해 😰 어려움.. (0) | 2021.10.21 |
---|---|
제곱수의 합 (0) | 2021.10.21 |
연속합 (0) | 2021.10.20 |
가장 긴 바이토닉 부분 수열 (0) | 2021.10.20 |
가장 긴 감소하는 부분 수열 (0) | 2021.10.20 |