[알고리즘]Sliding window - 최대 매출

3. 최대 매출
N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하는 프로그램

입력) 첫 줄에 N(5<=N<=100,000)과 K(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다.
출력) 첫 줄에 최대 매출액을 출력합니다.

 

참고) Sliding window

시간 복잡도 : O(N)

 

 

import java.util.Scanner;

public class Main { // 시간복잡도 O(n)
	
	public static int solution(int n, int k, int[] arr) {
		int answer = 0, sum = 0;
		
		for (int i=0; i<k; i++) sum += arr[i];				
		answer = sum;
		
		for (int i=k; i<n; i++) {
			sum += arr[i] - arr[i-k];
			answer = Math.max(answer, sum);
		}

		return answer;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt(); // n일 간의 매출기록
		int k = scanner.nextInt(); // 연속된 k일
		int[] arr = new int[n];
		for (int i=0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		System.out.println(solution(n, k, arr));
	}

}

---

결과