[BOJ/C++] 12847번 꿀 아르바이트

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

이 문제에서 구해야하는건 길이가 n인 배열에서 연속된 m개의 수의 합이 최대가 되는 것을 구하는 것

인덱스 처음부터 m까지의 수의 합을 구하는 방법도 있지만 m이 커질수록 중복된 연산이 많아짐

이때 생각해볼 수 있는게 누적합! 누적합 배열을 하나 만들어 m개의 수의 합을 중복 연산 없이 구하쟈

수가 매우 크므로 long long도 주의..!

#include <iostream>
using namespace std;

int n, m;
long long pay[100000];
long long pay_sum[100000];

int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> pay[i];
    }

    if (m == 0)
    {
        cout << 0;
        return 0;
    }

    pay_sum[0] = pay[0];
    for (int i = 1; i < n; i++)
    {
        pay_sum[i] = pay_sum[i - 1] + pay[i];
    }

    long long max_p = pay_sum[m - 1];

    for (int i = 1; i < n - m + 1; i++)
    {
        long long k = pay_sum[i + m - 1] - pay_sum[i - 1];
        if (max_p < k)
            max_p = k;
    }

    cout << max_p;
}