最大部分列和(Maximum Segment Sum、略してMSS)問題とは、与えられた整数列の部分列の和のうち最大のものを求めるという問題。 非常に簡単な例で言うと、 a = {-1, -1, 1, 1, 1, -1, -1}という数列の最大部分列和mss(a)は{1, 1, 1}の和の3になる。 他にも、 ## example a1 <- c(8, -3, 65, -20, -45, 100, 8, -17, 4, -14) ## mss(a1) => 113 = sum(8, -3, 65, -20, -45, 100, 8) a2 <- c(31, -41, 59, 26, -53, 58, 97, -93, -23, 84) ## mss(a2) => 187 = sum(59, 26, -53, 58, 97)といった具合になる。 全ての部分列を求めて比較する方法 すぐ思いつく