최대 매출

설명

현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.

만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면

12 1511 20 2510 20 19 13 15

연속된 3일간의 최대 매출액은 11+20+25=56만원입니다.

여러분이 현수를 도와주세요.

 

입력

첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.

두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.

 

출력

첫 줄에 최대 매출액을 출력합니다.

예시 입력 1 

10 3
12 15 11 20 25 10 20 19 13 15

 

예시 출력 1

56

 

소스 코드1

import java.util.Scanner;
//최대 매출
public class Main {
    public static int solution(int N, int K, int[] arr) {
        int ans = 0;

        int[] sum = new int[N - K + 1];
        for (int i = 0; i < K; i++) { //sum[0]에 합 입력
            sum[0] += arr[i];
        }

        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] - arr[i - 1] + arr[K + i - 1];//앞의 인덱스 합에서 맨 첫자리 빼고 그 다음자리 수 더하기
        }

        for (int i = 0; i < N - K + 1; i++) { //최댓값 구하기
            if (sum[i] > ans) {
                ans = sum[i];
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int arr[] = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(solution(N, K, arr));
    }
}

 

처음에는 이중 for문을 이용해서 간단하게 구현했었는데 시간초과가 걸려서

하나씩 다 더하는 방법보다는 배열을 이용하여 앞 뒤만 하나씩 빼고 더하여 계산하는 방식으로 하니 시간이 많이 줄어들었다.