データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
15: 2020/11/29(日)21:37:18.71 ID:M8xgBTYt(1/3)調 AAS
そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです．
max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
であると仮定する．
max_ending = max(0, max_ending+a)
を実行した後，
max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
が成り立つ．
39(1): 2021/10/05(火)03:31:33.71 ID:wQtjKuKa(2/2)調 AAS
>>38
定義は同じ
V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される
E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ
合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.012s