最大部分列和(Maximum Segment Sum、略してMSS)問題とは、与えられた整数列の部分列の和のうち最大のものを求めるという問題。 非常に簡単な例で言うと、 a = {-1, -1, 1, 1, 1, -1, -1}という数列の最大部分列和mss(a)は{1, 1, 1}の和の3になる。 他にも、 …