【Java】移動平均をスライディングウィンドウ法で算出

この記事で分かること

・移動平均の算出方法
・スライディングウィンドウ法の考え方

前提条件

Javaの基礎知識（配列）,コレクションクラス(AraayList)の知識

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

スライディングウィンドウ法は、連続する部分配列や部分区間に関する問題を効率的に解決するための手法である。この方法は、特に配列やリストの中で部分配列の合計や平均、最大・最小値を求める際に有用

使用パターン（どんな時に使うのか）

ここではざっくりにどんなケースがあるのかを記載する。コーディングは「実装」に記載

ケース1. 最大または最小の合計を持つ連続部分配列を求めたいとき

ex)整数配列が与えられたとき、固定サイズ K の連続部分配列の合計が最大または最小となる部分配列を見つける。

ケース2.指定された合計を持つ連続部分配列

ex)整数配列が与えられたとき、指定された合計 S を持つ連続部分配列が存在するかどうかを確認する。

ケース3. 売り上げデータ算出

ex)あなたはレストランで、連続する日数の売上データが記録されたリストを持っています。各日ごとの売上データが与えられるので、特定の連続する期間の売上の合計が最大となる期間を見つけてください。

実装方法

使用パターン(ケース3)を実装してみる。

ケース3問題文

あなたはレストランで、連続する日数の売上データが記録されたリストを持っています。各日ごとの売上データが与えられるので、特定の連続する期間の売上の合計が最大となる期間を見つけてください。

制約・ルール

・CSV想定として「,」区切りでデータを持つ
・連続する期間は「整数N」として範囲は[0 < N < 10]とする

売上の合計が最大となる N 日間の期間の開始日を出力すること。最も早い開始日が複数ある場合は、その中で最も早い期間を出力する。

実装（初学者よりミスがある可能性あり）

import java.util.ArrayList;
import java.util.Scanner;

public class Sample {
	public static void main(String[] args) {
		String data_days = "20240801,20240802,20240803,20240804,20240805,20240806,20240807,20240808,20240809,20240810";
		String data_sales = "10,20,15,6,7,4,18,21,24,4";

		//　移動平均の基準Nを出す
		Scanner scanner = new Scanner(System.in);
		System.out.println("何日分で計算する？");
		int N = scanner.nextInt();
		//try-catch割愛
		System.out.println("==================");

		String[] days = data_days.split(",");
		String[] sales = data_sales.split(",");

		ArrayList<Integer> daysList = new ArrayList<Integer>();
		ArrayList<Integer> salesList = new ArrayList<Integer>();

		// csvのデータを整数に変換し配列に格納
		for (String day : days) {
			daysList.add(convert(day));
		}
		for (String sale : sales) {
			salesList.add(convert(sale));
		}

		//移動平均のメソッドを使って最高売り上げになる初日を算出
		int maxDay = salesMaxScore(salesList, N);

		System.out.println(N + "連続する期間の売上の合計が最大となる期間は" + daysList.get(maxDay) + "です");
	}

	// String => int変換メソッド
	public static int convert(String str) {
		//try-catch割愛
		return Integer.parseInt(str);
	}

	// Nの移動平均を考え、最高売り上げの初日要素を導く
	public static int salesMaxScore(ArrayList<Integer> list, int N) {
		int maxScore = -1;
		int currentScore = 0;
		int startIndex = 0;

		// 初期の合計を計算
		for (int i = 0; i < N; i++) {
			currentScore += list.get(i);
		}
		maxScore = currentScore;

		// スライディングウィンドウで合計を計算
		for (int i = N; i < list.size(); i++) {
			currentScore += list.get(i) - list.get(i - N);
			if (currentScore > maxScore) {
				maxScore = currentScore;
				startIndex = i - N + 1;
			}
		}
		return startIndex;
	}
}