データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
15: デフォルトの名無しさん [] 2020/11/29(日) 21:37:18.71 ID:M8xgBTYt そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです． max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 であると仮定する． max_ending = max(0, max_ending+a) を実行した後， max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 が成り立つ． http://mevius.5ch.net/test/read.cgi/tech/1580131715/15
16: デフォルトの名無しさん [] 2020/11/29(日) 22:05:05.40 ID:M8xgBTYt 5, -7, 3, 5, -2, 4, -1 インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceは，3, 5, -2, 4です． インデックスが6で終わるsliceまたは空のsliceのうち，その和が最大であるsliceをSとする． Sは何になるか？ 3 + 5 - 2 + 4 - 1 = 9 > 0なので，Sは空のsliceではありません． Sは，例えば，5, -2, 4, -1ではありません．もし，Sが，5, -2, 4, -1であるとすると， 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1 したがって， 5 - 2 + 4 > 3 + 5 - 2 + 4 となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく， 5, -2, 4であるということになってしまうからです． Sは，例えば，-7, 3, 5, -2, 4, -1ではありません．もし，Sが，-7, 3, 5, -2, 4, -1であるとすると， -7 + 3 + 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1 したがって， -7 + 3 + 5 - 2 + 4 > 3 + 5 - 2 + 4 となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく， -7, 3, 5, -2, 4, -1であるということになってしまうからです． http://mevius.5ch.net/test/read.cgi/tech/1580131715/16
18: デフォルトの名無しさん [sage] 2020/11/29(日) 23:10:03.18 ID:M8xgBTYt そうですね． 足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね． http://mevius.5ch.net/test/read.cgi/tech/1580131715/18
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.014s