AOJ0516: Maximum Sum(累積和, しゃくとり法)

累積和としゃくとり法を知らなかったのでメモ。計算量を考えずに全探索までしていたので書いておく。最悪 O(n²) で最大 n = 100000 だから全探索はダメ(指数記号が出せない…)。

累積和

O(n)で速い。

// 累積和
// include略
int sum[100010];
int main(void)
{
    int n, k;
    while(1) {
        cin >> n >> k;
        if(n==0 && k==0) break;

        int a[n];
        for(int i=0; i<n; i++) cin >> a[i];
        for(int i=0; i<n; i++)
            sum[i+1] = sum[i] + a[i]; // sum[i] := a[0]からa[i-1]までの和(sum[0]=0)

        int ans = sum[k] - sum[0];
        for(int i=0; i<n-k; i++)
            ans = max(ans, sum[i+1+k] - sum[i+1]);
        cout << ans << endl;
    }

    return 0;
}

しゃくとり

これも O(n)。

// しゃくとり法
// include略
int ans, tmp;

int main(void)
{
    int n, k;
    while(1) {
        cin >> n >> k;
        if(n==0 && k==0) break;

        int a[n];
        for(int i=0; i<n; i++) cin >> a[i];
        ans = 0;
        for(int i=0; i<k; i++) ans += a[i];
        tmp = ans;
        for(int i=0; i<n-k; i++) {
            tmp = tmp + a[k + i] - a[i];
            ans = max(ans, tmp);
        }
        cout << ans << endl;
    }

    return 0;
}

全探索

O(nk) なので TLE します。

// 全探索
#include <algorithm>
#include <iostream>
using namespace std;

int main(void)
{
    int n, k;
    while(1) {
        cin >> n >> k;
        if(n==0 && k==0) break;

        int a[n];
        for(int i=0; i<n; i++) cin >> a[i]; 
        int ans, sum;
        ans = -114514810;
        for(int i=0; i<n-k+1; i++) {
            sum = 0;
            for(int j=i; j<i+k; j++) {
                sum += a[j];
            }
            ans = max(ans, sum);
        }
        cout << ans << endl;
    }
    return 0;
}

このサイトが参考になった。

paiza.hatenablog.com