C#でアルゴリズムとデータ構造1 ～最大部分配列問題～ - Qiita今日は最大部分配列問題（maximum-subarray problem）について。 最大部分配列問題とは 入力 要素数が1以上の1次元配列。 出力 入力の1次元配列の全ての部分配列（配列の一部をそのまま切り出したもの。要素の順序を並べ替えたり、一部の要素を取り除いたりしてはならない）の中で、部分配列のそれぞれの要素の値の総和が最大となるようなもの。 算法1 考え方 入力の1次元配列の全ての部分配列のそれぞれの要素の値の総和を計算し、総和が最大となるような部分配列を探し出せば良い。 全ての1次元配列の部分配列は、元の1次元配列と、左端の要素の番号と、右端の要素の番号から成る3つ組で表せる。たとえば、要素数が10の1次元配列Aの3つ目の要素から5つ目の要素までから成る部分配列は、正に、元の1次元配列と、左端の要素の番号である3と、右端の要素の番号である5から成る3つ組で表せる（これを、たとえ
