スライディングウィンドウ法とは？

今回の問題

「数値がN個入っている配列から連続したX個を取り出して合算したとき、最も高い合算値はいくらか」といった問題です。

当初のコード

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int maisu = sc.nextInt();//すべての寿司
        int eat = sc.nextInt();//食べる枚数
        int[] sushi = new int[maisu];
        int index = 0;//インデックス
        int cnt = 0;//繰り返し回数管理
        int sum = 0;
        int max = 0;//合計金額のうち最も高いもの
        //すべての寿司を格納
        for(int i = 0; i < maisu;i++){
            sushi[i] = sc.nextInt();
        }
        
        //寿司の組み合わせ(連続したeat枚)から、合計金額が最も高くなるもの
        for(int i = 0;i < sushi.length;i++){
            //回数と合計金額を初期化
            cnt = 0;
            sum = 0;
            //加算の開始位置を設定
            index = i;
            while(cnt < eat){
                //合計金額に加算
                sum += sushi[index];
                cnt++;//eatまで繰り返す
                index++;
                if(index == maisu){
                    index = 0;//indexが末尾まで到達したら先頭に戻る
                }
            }
            //maxとsumを比較
            max = Math.max(max,sum);
        }
        
        //最も高い合計金額を出力
        System.out.println(max);
    }
}

配列からX個取り出して合算、その時点での最大値と比較して大きいほうを格納、インデックスを一つずらしてX個合算、、をひたすら繰り返す実装です。

何が問題なのか?

このコードでも処理結果は正しいので、間違いではありません。
しかし、よく見ると無駄な箇所があります。
例

配列：｛1,2,3,4,5,6,7,8,9,10}//すべてのお寿司
　Ｘ：5 //配列から連続した5個の値を取得して合算する

このような場合で考えます。
当初のロジックでは、
①配列の0番目から5個を取得して合算する
②一つずらし、配列の1番目から5個を取得して合算する
という処理を配列の個数分ひたすら繰り返していました。
しかし、これに値を当てはめてみると、
①1 + 2 + 3 + 4 + 5
②2 + 3 + 4 + 5 + 6
となり、間の数字である2,3,4を都度足していることがわかります。
つまり、合算する範囲の両端以外の数値は前回の数値と変わらないということです。
この無駄を解消するのが、スライディングウィンドウ法です。

スライディングウィンドウ法とは

スライディングウィンドウ法とは、連続した部分列の合計や最大値を求める際に、計算結果を再利用して効率的に処理する手法です。具体的には、最初に一度だけ部分列の合計を計算し、その後、部分列の端を一つずつスライドさせることで新たな合計を得る方法です。これにより、無駄な計算を減らし、効率的に問題を解くことができます。

スライディングウィンドウ法を用いたコード

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int maisu = sc.nextInt();//すべての寿司
        int eat = sc.nextInt();//食べる枚数
        int[] sushi = new int[maisu];
        int sum = 0;
        int max = 0;//合計金額のうち最も高いもの
        //すべての寿司を格納
        for(int i = 0; i < maisu;i++){
            sushi[i] = sc.nextInt();
        }
        //最初の合計金額算出(1)
        for(int i = 0;i < eat;i++){
            sum += sushi[i];
        }
        max = sum;
        //スライドで算出(2)
        for(int i = 1;i < maisu;i++){
            //左端の寿司を減らす
            sum -= sushi[i - 1];
            //右端を足す
            sum += sushi[(i + eat - 1) % maisu];
            //最も高い合計金額を出力
             max = Math.max(max,sum);
        }
        
        //最も高い合計金額を出力
        System.out.println(max);
    }
}

配列：｛1,2,3,4,5,6,7,8,9,10}//すべてのお寿司
　Ｘ：5 //配列から連続した5個の値を取得して合算する

同じ例で示します。
今回のロジックでは、
①配列の0番目から5個を取得して合算する
②①の合算値から、左端の値を引く
③①の合算値に、右端の一つ右の値を足す
(以降、一つずつずらしながら②と③を繰り返す)
といった処理となります。

値を当てはめてみると、
①1 + 2 + 3 + 4 + 5 = 15
②15 = 15 - 1(左端の値を引く)
③14 = 14 + 6(右端の一つ右の値を足す)
といった具合で、無駄な計算が減りよりシンプルになりました。

まとめ

全探索は計算量が非常に多く厄介ですが、スライディングウィンドウ法を用いてシンプルに実装できる場合もあります。
ぜひ参考にしてみてください!