【スタック・キューメニュー】最大の区間和 (paizaランク B)-解答例-PHP編

2022年7月16日

【スタック・キューメニュー】> STEP: 2 最大の区間和 (paizaランク B 相当) [難易度: 2124 ±46]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

N 個の要素からなる数列 A があります。 A に含まれる連続した X 個の要素の和の最大値とその区間の左端の値を出力してください。ただし、要素の和の最大となる区間が複数ある場合はそのうちもっとも先頭の値を出力してください。
たとえば、 N = 4 , A = [2, 3, 4, 1] , X = 2 とします。連続した 2 個の要素の和が最大となる区間は A の 2 番目から 3 番目まで( 3 + 4 = 7 が最大値 )なので、最大値 7 とその区間の左端の値 3 を出力します。

また、実行時間に注意しましょう。たとえば以下の Python3 のプログラムのような、数列の要素数 N と和を求める連続する要素数 X を用いて、約 N * X 回足し算をおこなうプログラムはタイムオーバーになってしまうことがあります。キューまたはスタックを用いて効率のよいプログラムを意識しましょう。

入力値（例）
4 2
2 3 4 1

出力値（例）
7 3

解答例

<?php
    list($n, $x) = explode(" ", trim(fgets(STDIN)));
    $a = explode(" ", trim(fgets(STDIN)));
    
    $total_max = 0;
    $left_num = $a[0];
    
    for ($i = 0; $i < $x; $i++) {
        $total_max += $a[$i];
    }
    
    $tmp_sum = $total_max;
    
    for ($i = 0; $i < ($n - $x); $i++) {
        $tmp_sum -= $a[$i];
        $tmp_sum += $a[$i + $x];
        
        if ($tmp_sum > $total_max) {
            $left_num = $a[$i + 1];
            $total_max = $tmp_sum;
        }
    }
    
    printf("%d %d\n", $total_max, $left_num);
?>

<?php

list($n, $x) = explode(" ", trim(fgets(STDIN)));

$a = explode(" ", trim(fgets(STDIN)));

$total_max = 0;

$left_num = $a[0];

for ($i = 0; $i < $x; $i++) {

$total_max += $a[$i];

}

$tmp_sum = $total_max;

for ($i = 0; $i < ($n - $x); $i++) {

$tmp_sum -= $a[$i];

$tmp_sum += $a[$i + $x];

if ($tmp_sum > $total_max) {

$left_num = $a[$i + 1];

$total_max = $tmp_sum;

}

printf("%d %d\n", $total_max, $left_num);

解答例

カテゴリー