[Baekjoon] 5591_最大の和

문제(출처: https://www.acmicpc.net/problem/5591)

---

< 最大の和 >

 

문제 풀이 

 

슬라이딩 윈도우 알고리즘을 사용하여 문제를 해결한다.

[2 5 -4] 10 3          -> 합: 3
2 [5 -4 10] 3          -> 합: 11
2 5 [-4 10 3]          -> 합: 9

 

 

my solution (Java)

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

public class _5591_ { // 最大の和

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int arr[] = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}

		int start = 0, end = k, sum = 0;
		for (int i = start; i < end; i++) {
			sum += arr[i];
		}

		int max = sum;

		while (end < n) {
			sum -= arr[start];
			start += 1;

			sum += arr[end];
			end += 1;

			max = Math.max(max, sum);
		}

		System.out.println(max);
	}
}

변수)
n, k : 입력 개수, 합 개수
arr : 입력값
start, end : 시작 위치, 끝 위치
max, sum : 최댓값, 합

 

입력 개수와 합해야 하는 개수를 입력받는다. n개만큼 정수를 입력받아 배열 arr에 저장한다. 배열 0번째부터 k개를 합해 sum과 max 값을 업데이트한다. end 값이 n보다 작을 때 다음 과정을 반복한다.

 

1) arr[start] 값 빼기

2) start+1

3) arr[end] 값 더하기

4) end+1

5) max 값 업데이트

 

최종 max를 출력한다. 

---

---