[BOJ알고리즘, C++]#2559_수열의 최대 구간 합, 누적 합 알고리즘

[BOJ 알고리즘, C++] #2559_수열의 최대 구간 합, 누적 합 알고리즘 

 

BOJ 알고리즘 문제 풀이, 2559_수열

누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제

 

 

---

 

문제

 

풀이

 

수열 중 주어진 구간 중 최대 합을 찾는 문제입니다.

앞서 살펴봤던 11659번 문제와 풀이 과정이 같습니다(아래 링크를 참조하세요)

[BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘

 

먼저, 입력받은 수열들의 누적 합을 따로 vector 컨테이너에 저장합니다.

주어진 구간( Left ~ Right )의 합을 구하는 공식, "PreSum[Right] - PreSum[Left - 1]",을 활용하면 쉽게 풀 수 있는 문제입니다.

 

따라서, 풀이는 간단합니다.

수열의 첫 번째 항목부터 주어진 구간 안에서 합을 구해가며, N( 수의 개수 ) - Interval + 1에 도달할 때까지 최대 구간 합을 업데이트하는 알고리즘을 작성합니다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

vector<ll> preSum(1, 0);
int N, K;

ll MaxSum(int interval)
{
    ll tmpSum = -9999;
    for(int i=1; i <= N-interval+1; ++i )
    {
    	// 구간의 Right = i + interval -1, Left = i - 1
        if(tmpSum > preSum[i + interval - 1] - preSum[i-1])
            continue;
        else
            tmpSum = preSum[i + interval - 1] - preSum[i-1];
    }
    return tmpSum;
}

int main()
{
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
    
    cin >> N >> K;
    
    int tmp;
    for(int i=1; i<=N; ++i)
    {
        cin >> tmp;
        
        preSum.push_back(preSum[i-1] + tmp);
    }
    
    ll result;
    result = MaxSum(K);
    
    cout << result << endl;
}