連続部分列の最大和を求めるときの主要3つのアルゴリズム
整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。
手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）
あるインデックス i で終了する連続部分配列の最大 ...
6月3日 22:26 投稿
最大部分配列問題の解法
最大部分配列問題
この記事では、最大部分配列問題の様々な解法について説明します。より詳細なアルゴリズムの考え方は「アルゴリズムイントロダクション」を参照してください。
部分配列構造体
typedef struct {
int start, end, total;
} SubArray;
力まかせ法による解法
すべての配列区間の和を計算して最大部分配列を見つける方法です。アルゴリズムの複雑さはθ( ...
5月30日 12:40 投稿