Ark's Blog

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