백준 13398번 연속합 2 자바 Java (☆공부 283일차)

133398 연속합 2

 

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

13398번: 연속합 2

 

 

 

---

백준 13398번 문제 연속합 2

---

문제

---

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	19492	5867	4352	29.664%

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

제한

 

예제 입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

54

힌트

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/276

공부 143일차: 백준 13398번 연속합 2 자바 java

4달 전에 푼 문제

 

 

두 가지 방법을 소개하고 있는데, 이 중 왼쪽/오른쪽으로 나누어 구하는 방법이 재미있어 보였다

(다른 블로그들이 다 2차원 배열만 있기도 하고)

원리를 그림으로 표현하면 위와 같다

i를 제외한 연속합은 dpR[i-1] + dpL[i+1]가 되는 것이다

 

 

 

---

정답 인정 코드

---

 

public class Main {
 
    public static void main(String[] args) throws Exception{
        int n = read();
        int[] arr = new int[n];
        int[] dpR = new int[n];
        int[] dpL = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = read();
            dpR[i] = dpL[i] = arr[i];
        }
 
        int max = dpR[0];
        for(int i = 1; i < n; i++) {
            dpR[i] = Math.max(dpR[i], dpR[i-1]+arr[i]);
            max = Math.max(max, dpR[i]); 
        }
        for(int i = n-2; i >= 0; i--) {
            dpL[i] = Math.max(dpL[i], dpL[i+1]+arr[i]);
        }
        
        for(int i = 1; i < n-1; i++) {
            int exceptI = dpR[i-1]+dpL[i+1]; 
            max = Math.max(max, exceptI);
        }
        System.out.println(max);        
    }
 
    static int read() throws Exception {
        int c, n = System.in.read() & 15;
        boolean isNegative = n == 13;
        if (isNegative) n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) {            
            n = (n << 3) + (n << 1) + (c & 15);
        } 
        return isNegative ? ~n + 1 : n;
    }
}
 

 

 

 

---

이 블로그를 참고해서 음수도 read() 메서드를 사용할 수 있게 했다