2559번: 수열 [JAVA]

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

2559번: 수열

 

접근 방식) 누적합

1. 입력받은 온도 수열을 누적합 배열로 저장한다.

    누적합 배열은 prefixSum[i] = prefixSum[i - 1] + 현재입력값

    으로 저장하기 위해서 int[] prefixSum = new int[N + 1]; 로 생성한다.

2. K부터 누적합배열 끝까지 돌면서, K일의 온도 합이 max값보다 크면 max를 업데이트해준다.

    ex) index 2 ~ 5 까지의 누적합은?

          → prefixSum[5] - prefixSum[2 - 1]

3. 결과값 : max값 출력

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B_2559 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());   // 전체 날짜 수
        int K = Integer.parseInt(st.nextToken());   // 연속 날짜 수
        int[] prefixSum = new int[N + 1];           // 누적합 배열

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            prefixSum[i] = prefixSum[i - 1] + Integer.parseInt(st.nextToken());
        }
        
        // 배열 전체 돌면서, K개씩 누적합 계산하며, max값 업데이트
        int max = Integer.MIN_VALUE;
        for (int i = K; i <= N; i++) {
            max = Math.max(max, prefixSum[i] - prefixSum[i - K]);
        }
        System.out.println(max);
    }
}