백준 2559: 수열 [누적합][구간합] -Java

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

2559번: 수열

 

연속한 수 K의 합이 가장 큰 값을 계산하는 알고리즘이다.

(i-K-1) ~ (i) 까지의 합을 sum[i]에 저장함

한칸씩 이동하면서 i-K 값만 반대로 연산해주고 현재 위치의 값을 더해주면 된다.

 

<Java 코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		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 arr[] = new int[N+1];
		int sum[] = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			
			if(i<=K)
				sum[i] = sum[i-1]+arr[i]; //K번째 까지는 1부터 모든수를 다 더한 누적합 구함.
			
		}
		
		//k만큼 연속하는 수 범위만큼 계산, 누적합배열에 저장
		int maxVal = sum[K];
		for (int i = K+1; i <= N; i++) {
			sum[i] = sum[i-1]+(arr[i-K]*(-1))+arr[i];
			maxVal = Math.max(maxVal, sum[i]);
		}
		
		System.out.println(maxVal);
	}

}