boj 2559 수열

www.acmicpc.net/problem/2559

2559번: 수열

모든 연속적인 K일 간의 최대 온도의 합을 출력하는 문제입니다.

우선 dp를 이용하여 N일 간 측정한 모든 온도의 연속합을 저장합니다.

그 다음 투 포인터 방식으로 l = 1, r = K으로 시작하여 dp[r] - dp[l - 1]의 최댓값을 구해주시면 됩니다.

 

 

import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[], dp[];
    static int N, K, ans = Integer.MIN_VALUE;
 
    static void func() {
        int l = 1;
        int r = K;
 
        while (r <= N) {
            ans = Math.max(ans, dp[r] - dp[l - 1]);
 
            r++;
            l++;
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        list = new int[N + 1];
        dp = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
            dp[i] = dp[i - 1] + list[i];
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}