しゃくとり法を使って、要素の和が M を超えないような A の部分列の最大の長さを求めたい。
- 評価
- クリップ 0
- VIEW 335
前提・実現したいこと
しゃくとり法を使って、要素の和が M を超えないような A の部分列の最大の長さを求めたいのですがうまくいきません。
考えている構造はこのような形です、が、最大の長さがうまくでなくて困っています。
発生している問題・エラーメッセージ
[リンク内容](http://)
エラーメッセージは出ないですが区間の最大値と異なる値が出ます。
該当のソースコード
<?php
/*
数列 A の要素数 N と値 M、その要素 A_1, A_2 ... A_N が与えられます。
要素の和が M を超えないような A の部分列の最大の長さを求めてください。
*/
//取得
$input = explode(" ",trim(fgets(STDIN)));
$num = $input[0];
$m = $input[1];
$a = explode(" ",trim(fgets(STDIN)));
//累積和を求める
$sum[0] = 0;
for($i=0; $i<$num; $i++){
$sum[$i+1] = $sum[$i] + $a[$i];
}
//処理
$ok_flag = false; //reset
$right = 1;//区間の右端
for ($left = 1; $left < $num; $left++) {
while($right < $num){
if($sum[$right] - $sum[$left] < $m){
$ok_flag = true;
$right++;//右に伸ばせるだけ伸ばす
}else{
//右に伸ばせなくなったのでその時点を格納
$save[] = $right-$left;
break;
}
}
}
//出力
if($ok_flag==false){
echo(0);
}else{
echo(max($save));
}
?>試したこと
Aが10万個の整数のバリエがあるため、累積和としゃくとり法について調べました。しゃくとり法は区間の左端を固定し右端をのばすということで、区間の右端を伸ばせるだけ伸ばし、伸ばせなくなったら区間数を配列$saveに格納するようにしました。
補足情報（FW/ツールのバージョンなど）
しゃくとり法について調べるきっかけになった問題元はこちらですが、この問題を解きたいというよりしゃくとり法が実装できるように理解したいです。
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
まだ回答がついていません
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.23%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
質問への追記・修正の依頼
2020/10/21 13:13
複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。
karasumaru
2020/10/22 11:09
失礼いたしました。
試したことと、実現したいことに図表などを追加しました。