最大部分列和のDP
curは各位置で終わる連続和の最大。maxSumはcurの最大を保持とは？
意味
この手続は連続する部分列の和の最大値を求めるアルゴリズム(いわゆる最大部分和)で、直前までの和に今の要素を足すか、今の要素から始め直すかを毎回選ぶ。 ▍なぜ正解 curは「その要素で終わる連続和の最大」を保持する。i=2でcur=3,i=3でcur=2,i=4でcur=6,i=5でcur=4と変化し、maxSumは3→6と更新される。最終的にmaxSum=6(部分列{3,-1,4}の和)となる。 ▍よくある間違い 正の要素だけを足す、または全要素を合計してしまう。 ▍試験の狙い 最大部分和は「継続 vs 始め直し」の分岐と、最大値の別変数更新を分けて追う。
?応用情報技術者試験での問われ方
配列 a = {-2, 3, -1, 4, -2}(添字は1から)に対し擬似コードを実行する。最後に出力されるmaxSumの値はいくつか。
答え：curは各位置で終わる連続和の最大。maxSumはcurの最大を保持
✓覚え方
足して得なら続け、損なら仕切り直す。
「curは各位置で終わる連続和の最大。maxSumはcurの最大を保持」を、演習で定着させる。
無料ではじめる →応用情報技術者試験の過去問を、一問ごとの8-ways解説つきで。まずは無料で。
登録は1分・クレジットカード不要。無料のまま練習・暗記カード・模試まで使えます。
ukamiru 用語集 · 応用情報技術者試験