코드트리 [자바 java] 정수 n개의 합 2

https://www.codetree.ai/missions/8/problems/sum-of-n-integers-2?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

배열이 주어지고, m이 주어질 때 m만큼의 연속된 인덱스를 더했을 때의 최댓값을 구하는 문제이다. 

이를 부분합을 이용해서 풀어보았다.

 

이와 같이 특정 인덱스의 앞부분을 모두 더한 배열을 만들고, m만큼의 간격을 두고 뺀 값을 max로 갱신했다.

 

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


public class Main {
    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 m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        int[] arr = new int[n+1];
        int[] hap = new int[n+1];

        for(int i = 1;i<=n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
            hap[i] = hap[i-1] + arr[i];
        }
        int max = Integer.MIN_VALUE;

        for(int i = 0;i<n-m;i++){
            max = Math.max(max,hap[i+m] - hap[i]);
           // System.out.println(max);
        }

        System.out.println(max);

        
    }
}