この記事はSunrise Advent Calendar 2019の9日目の記事です。 adventar.org 内容はごった煮ということなので、アルゴリズムと代数について書きます。 TL; DR Kadane's algorithmと呼ばれる最大部分配列問題をで解くアルゴリズムがある。 このアルゴリズムは…

半環上の最大部分配列問題とKadane's algorithm