문제

이해

주어진 수열의 연속된 구간 합을 구하되 최대값을 구해야 한다.

접근

누적합 알고리즘을 사용하면 쉽게 해결할 수 있다.

입력받을 때 누적합을 배열에 저장한 뒤 K에 대해 각 구간합의 크기를 비교한다.

코드

package java_baekjoon;

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

public class prob2559 {
    static int N;
    static int K;
    static int[] sum;
    static int max = Integer.MIN_VALUE;

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

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        K = Integer.parseInt(input[1]);
        sum = new int[N + 1];

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

        for (int i = K; i <= N; i++) {
            max = Math.max(max, sum[i] - sum[i - K]);
        }

        System.out.println(max);
    }
}

답이 될 max는 min_value로 선언했다. 왜냐하면 수열의 온도는 -, + 모두 값으로 가질 수 있어 0으로 선언하면 안되기 때문이다.

결과