CS/알고리즘_문제풀이(자바)

연속합 2

Jedy_Kim 2021. 10. 21. 18:13
728x90

https://www.acmicpc.net/problem/13398

 

13398번: 연속합 2

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

www.acmicpc.net

// 코드

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