POH Lite4 エンジニアでも恋がしたい-転職初日にぶつかった女の子が同僚だった件 ミッション3

ミッション1 / ミッション2 / ミッション3 / 共通解

<?php
	$input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
	
	$una = array_shift($input);
	$una = explode(' ', $una);
	$max = 0;
	
	for($i=0; $i<$una[1]; $i++){
		$tmp =  array_sum(array_slice($input, $i, $una[0]));
		if($tmp > $max){
			$max = $tmp;
		}
	}
	print($max);

問題文にある解き方をそのままなぞっただけです。
とっても簡単。

https://paiza.jp/poh/enkoi-ending/e9dcd311
なん…だと！？
単純にやり過ぎたようだ。
答えは合ってるはずだが、効率が悪すぎてタイムオーバーになってしまいました。
もう少し効率の良い方法を考えてみましょう。

<?php
	$input = file('php://stdin', FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
	
	$una = array_shift($input);
	$una = explode(' ', $una);
	$now =  array_sum(array_slice($input, 0, $una[0]));
	$max = $now;
	
	for($i=$una[0]; $i<$una[1]; $i++){
		$now = $now + $input[$i] - $input[$i-$una[0]];
		if($now > $max){
			$max = $now;
		}
	}
	print($max);

https://paiza.jp/poh/enkoi-ending/5d116982
見事にハワイでハネムーンをゲットしました。

動作をサンプルで解説します。
まず左端の4+5+1=10点を前提として計算、MAXも10点と仮置きし、ここをスタート地点とする。
次に右隣の10点をプラス、左端の4点をマイナスすると、これが次の5+1+10=16点となる。
現在のMAX10点を超えているので最大値を更新。
次に右隣の3点をプラス、左端の5点をマイナスすると、これが次の1+10+3=14点となる。
現在のMAX16点以下なのでそのまま。
これを右端に移動するまで繰り返す。

最初のやつに比べて計算量が激減し、全テストケースを時間内に解くことができました。
というわけで、今回は最後まで簡単でした。

しかし正直、このゲーム絶対つまらないだろ。