2019-05-28から1日間の記事一覧

木で値を探しながら経路(path)も保存するbfs

例 https://www.geeksforgeeks.org/lowest-common-ancestor-binary-tree-set-1/ 内容 bfsの引数に vector &path も渡して入れていく 奥まで見に行って見つからなかったら path.pop_back() して詰めたものをキャンセルする

kadane's algorithm ~部分和をO(N)~

用途 負の値も含みうる数値配列にて、隣接した部分和の最大値をO(N)で求める 読み方はカダネではなく、ケイデインズ 最大部分列和(maximum segment sum)と言われる 例1 1 2 3 -2 5の場合 answer : 9 例2 -2 1 -3 4 -1 2 1 -5 4 answer : 6 例3 -1 -2 -3 answ…