【アルゴリズム】スライディングウィンドウアルゴリズム

スライディングウィンドウアルゴリズムについて説明します

0. 使用言語

C++14

1. スライディングウィンドウアルゴリズムとは

スライディングウィンドウアルゴリズムとは, 「配列内にある特定の範囲（ウィンドウサイズ）の配列に着目してアプローチを行い, アプローチ後に範囲をひとつずらして, またアプローチをする」という方法を繰り返していくアルゴリズムです。イメージは以下のようになります。

[1, 2, 7, 3, 88, 0, 9] という配列があり, ウィンドウサイズが3のとき
1. [1, 2, 7] でアプローチ, ひとつずらす
2. [2, 7, 3] でアプローチ, ひとつずらす
3. [7, 3, 88] でアプローチ, ひとつずらす
4. [3, 88, 0] でアプローチ, ひとつずらす
5. [88, 0, 9] でアプローチ
6. 終わり

2. 使用例

2.1 例題

[1, 2, 7, 3, 88, 0, 9]という配列があり, 配列内の3つ隣り合った数値の合計値の最大値を見つける。

2.2 ソースコード

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 7, 3, 88, 0, 9};
    int window_size = 3;

    int sum;
    int max = -1;

    for(int i=0; i<=vec.size()-window_size; i++) {
        sum = 0;
        for (int j=i; j<i+window_size; j++) {
            sum += vec[j];
        }
        
        if (sum > max) {
            max = sum;
        }
    }

    cout << "max: " << max << endl;
    return 0;
}