c++ 누적합

전 범위에 걸쳐 일정 갯수의 연속된 수들의 합을 구하는 알고리즘.

[준비 사항]

1. 첫 요소부터 시작하여 각 항에 누적된 수를 저장하는 배열을 먼저 구함.    예) sum[n] = sum[n-1] + a[n] 

 

[계산 방법]

k = 연속된 숫자 수

• f(i,k) = sum[i+k-1] - sum[i-1]    // i 번째 부터 k 수만큼의 누적합
• f(j,k) = sum[j] - sum[j-k]             // j번째 까지 k 수만큼의 누적합

 

 

j 번째 까지 k갯수의 누적합 코드 작성

  vector<int> n = { 3, - 2, - 4, - 9, 0, 3, 7, 13, 8, - 3 };
    int k = 5;
    vector<int> sums(nums.size()+1, 0);

    for (int i = 1; i < sums.size(); ++i)
    {
        sums[i] = sums[i - 1] + n[i-1];
    }

    int Max = -100000;
    for (int i = k; i < sums.size(); ++i)
    {
        Max = max(Max, sums[i] - sums[i-k]);
    }
    cout << Max << endl;