[BOJ / C++] 5591번 : 最大の和 (최대합)

문제

n 個の整数からなる数列 a1, a2, ..., an と正整数 k (1 ≤ k ≤ n) が与えられる．この とき，連続して並ぶ k 個の整数の和　 Si = ai + ai+1 + ... +ai+k−1 (1 ≤ i ≤ n−k + 1) の最大値を出力するプログラムを作りなさい．

 

n개의 정수로 이루어진 수열 a1, a2, ..., an과 양의 정수 k가 주어진다. 이때, 연속하여 늘어선 k개의 정수의 합 Si = ai + ai + 1 + .. + ai + k - 1의 최대값을 출력하는 프로그램을 작성하시오.

입력

1 行目には正整数 n (1 ≤ n ≤ 100000) と正整数 k (1 ≤ k ≤ n) がこの順に空白で 区切られて書かれている．2 行目以降の第 1 + i 行目 (1 ≤ i ≤ n) には，数列の i 番 目の項 ai (−10000 ≤ ai ≤ 10000) が書かれている．

 

첫째줄에는 양의 정수 n과 양의 정수 k가 공백으로 구분되어 주어진다.

두번째줄부터의 1 + i행째에는 수열 i번째의 ai가 주어진다.

출력

1 行だけからなり，その 1 行は Si の最大値だけを含む．

 

첫째줄에 Si의 최대값을 출력한다.

Solved.ac 레벨

실버 IV

풀이

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k,sum = 0, ans = -9999999;
    vector<int> v;
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        v.push_back(input);
    }

    for(int i = 0; i < k; i++) {
        sum += v[i];
    }

    for(int i = k; i < n; i++ ) {
        sum += v[i] - v[i - k];
        ans = max(ans, sum);
    }

    cout << ans << "\n";



    return 0;
}

윈도우의 크기가 k인 슬라이딩 윈도우 기법을 통해 연속하는 부분수열의 합 중 최대값을 찾는 간단한 문제다.

 

5591번: 最大の和