[백준] 1912번 - 연속합 [Java]

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

 

[백준] 1912번 - 연속합 [Java]

[백준] 1912번 - 연속합 [Java]

---

1.  아이디어

 

누적합 배열을 활용하면 O(N)으로 해결할 수 있다.

---

2. 문제풀이

 

N이 최대 10만이어서 O(N^2) 보다 빠른 풀이로 해결해야 했다.

다이나믹 프로그래밍의 누적합 배열을 활용하면 간단하게 해결할 수 있는데 누적합 배열을 생성한 후 누적합 배열을 순회하며 해당 인덱스 까지의 누적합과 해당 인덱스보다 작은 인덱스 범위에서 누적합의 최솟값의 차를 구하고 이러한 차의 최댓값을 구하면 연속합을 구할 수 있다.

누적합 배열을 통해 문제를 푸는 과정에서 연속합을 구할 때 인덱스가 큰 쪽에서 작은 쪽은 빼야 구간이 나온다는 점에 주의해야한다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] prefixSum = new int[1 + N];
        int min = 0;
        int ans = Integer.MIN_VALUE;

        for (int i = 1; i <= N; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i - 1];
            min = Math.min(min, prefixSum[i - 1]);
            ans = Math.max(ans, prefixSum[i] - min);
        }

        System.out.println(ans);
    }
}

---

4. 후기