Kadence のアルゴリズム: 最大合計連続サブ配列
サラ・チェン
⚡ スマートサマリー
カダネのアルゴリズムは、線形時間で最大合計連続部分配列を見つけます。 trac考えられるすべての部分配列を走査する代わりに、最大値を動的に求める。この古典的な動的計画法の手法は、株式、金融、シグナル問題に活用されている。
最大合計連続部分配列とは何ですか？
サブ配列は配列の連続した部分です。 配列の単一要素または配列の一部を指定できます。 最大和連続部分配列とは、最大和値を持つ部分配列を意味します。
例えば、配列 {-10, 5, 1, 6, -9, 2, -7, 3, -5} を考えてみましょう。この配列の部分配列は、{-10, 5, 1, 6}、{5, 1, 6}、{2, -7, 3, -5} などになります。しかし、{5, 1, 6, 3} は要素が連続していないため、部分配列にはなり得ません。
よく見ると、すべての部分配列の中で、強調表示されている部分配列 {5, 1, 6} の合計値が最大であることがわかります。
部分配列 {5, 1, 6} の合計は 12 であり、これは上記の配列のすべての可能な部分配列の中で最大の合計値です。したがって、この配列の場合、連続する部分配列の中で最大の合計値を持つのは {5, 1, 6} です。
連続部分配列の最大和を求めるためのシンプルなアプローチ
この問題を解決する簡単な方法は、XNUMX つのループを使用してすべての部分配列を見つけ、合計を計算し、その最大値を見つけることです。
以下は、連続する部分配列の合計が最大となる部分配列を見つけるための単純な方法を示すフローチャートです。これは、考えられるすべての部分配列を順に調べていく総当たり方式です。
これを行うための簡単な手順を次に示します。
ステップ1） 初期化します 最大合計 最小の整数値で設定し、 始まる (NAIST) と end ゼロに。
ステップ2） しましょう i (NAIST) と j 配列インデックスは j より大きいか等しい i; i サブアレイの開始を示し、 j その終わり。
ステップ3） 現在の合計 累積合計を保持します。更新ごとに、 現在の合計 より大きい 最大合計.
ステップ4） If 現在の合計 より大きい場合は、 最大合計 それと。
ステップ5） j 配列の末尾に達したら、インクリメントする i リセットします 現在の合計 0へ。
ステップ6） まで繰り返す i 配列の末尾に到達します。 最大合計 そして、最大のサブアレイ合計値を保持します。
ニックネーム Code シンプルなアプローチ
function maximumSubarraySum(): input: array for all possible subArray from array: calculate sum of each subarray store the maximum subArray return the maximum sum
C++ シンプルなアプローチの実装
#include <stdio.h> #include <iostream> using namespace std; void maximumSubarraySum(int array[], int n) { int max_sum = -1e9; int begin = 0; int end = 0; for (int i = 0; i < n; i++) { int current_sum = 0; for (int j = i; j < n; j++) { current_sum += array[j]; if (max_sum < current_sum) { max_sum = current_sum; begin = i; end = j; } } } cout << "largest sum is " << max_sum << endl; cout << "largest sum contiguous subarray: "; for (int i = begin; i <= end; i++) { cout << array[i] << "\t"; } } int main() { int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5}; maximumSubarraySum(array, sizeof(array) / sizeof(array[0])); }
出力：
largest sum is 12 largest sum contiguous subarray: 5 1 6
Python シンプルなアプローチの実装
def maximumSubarraySum(numbers): max_sum, begin, end = -1e9, 0, 0 for i in range(len(numbers)): current_sum = 0 for j in range(i, len(numbers)): current_sum += numbers[j] if max_sum < current_sum: max_sum = current_sum begin, end = i, j print("largest sum is ", max_sum) print("largest sum contiguous subarray: ", end='') for i in range(begin, end + 1): print(numbers[i], end='\t') numbers = [-10, 5, 1, 6, -9, 2, -7, 3, -5] maximumSubarraySum(numbers)
出力：
largest sum is 12 largest sum contiguous subarray: 5 1 6
カダネのアルゴリズムによる最大合計連続部分配列の探索
カダネのアルゴリズムは、2つのループではなく1つのループを使用する動的計画法です。少なくとも1つの値が非負であれば、正の数と負の数が混在する配列も処理できます。
連続する部分配列の合計が最大となる値を見つけるには、2つの変数のみが必要です。フローチャートは以下のとおりです。
Kadane のアルゴリズムの手順は次のとおりです。
ステップ1） 2 つの変数を作成します。 現在の合計 (NAIST) と 最大合計.
現在の合計 特定の配列インデックスで終了する最大合計値を保持し、 最大合計 これまでに観測された最大の合計値を格納します。
ステップ2） 各配列要素を 現在の合計次に、以下の2つの条件を確認してください。
- If 現在の合計 現在の要素より小さい場合、 現在の合計 現在の要素になります。
- If 最大合計 よりも少ない 現在の合計をタップし、その後、 最大合計 になる 現在の合計.
ステップ3） 前の手順を配列全体に対して繰り返した後、 最大合計 連続する部分配列の中で最大の和値を持つ。
Kadane のアルゴリズムの例
本稿では、小さな配列を用いてカダネのアルゴリズムを実証し、連続する部分配列の合計が最大となる部分配列を見つけるまでのすべてのステップを順を追って説明します。
与えられた配列が以下のようになっていると仮定しましょう。
カダンのアルゴリズムの手順は以下のとおりです。
ステップ1） 2 つの変数を作成します。 現在の合計 (NAIST) と 最大合計INT_MIN を代入します 最大合計 ゼロから 現在の合計ここで、INT_MINは最小の整数値を表します。
ステップ2） インデックス 0 の値は 4 です。したがって、 現在の合計 = 0 + 4 = 4。 現在の合計 より大きい 最大合計, 最大合計 4 になります。
ステップ3） インデックス 1 の値は -2 です。したがって、 現在の合計 = 4 + (-2) = 2。
今回 現在の合計 よりも少ない 最大合計結果として、 最大合計 更新されません。
ステップ4） 次の値は 1 です。 現在の合計 3を与える。 最大合計 （４）は依然としてより大きい 現在の合計, 最大合計 更新されません。
ステップ5） インデックス3では、値は3です。 現在の合計 3で 現在の合計 = 6。
この場合、 最大合計 より小さい 現在の合計ので、 最大合計 の値で更新されます 現在の合計.
ステップ6） 配列の最後の要素は -1 です。 現在の合計 5 を与えるが、これは 最大合計。 そう、 最大合計 残り6。
配列の末尾に到達したので、アルゴリズムはここで終了します。 最大合計 最大合計値である6が含まれています。部分配列は{4, -2, 1, 3}です。
ニックネーム Code カダンのアルゴリズムについて
function KadaneAlgorithm(): input: array maximum_sum, current_sum = 0 for each element in array: add the element with current_sum if current_sum is greater than the maximum_sum then maximum_sum = current_sum if current_sum is less than the element then current_sum = element return the value of maximum_sum
C++ Kadaneのアルゴリズムの実装
#include <iostream> using namespace std; void kadane(int array[], int n) { int current_sum = 0; int max_sum = -1e9; // -1e9 means -1,000,000,000 for (int i = 0; i < n; i++) { current_sum += array[i]; if (max_sum < current_sum) { max_sum = current_sum; } if (current_sum < array[i]) { current_sum = array[i]; } } cout << "largest sum is " << max_sum << endl; } int main() { int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5}; kadane(array, sizeof(array) / sizeof(array[0])); }
出力：
largest sum is 12
Python Kadaneのアルゴリズムの実装
def kadane(numbers): current_sum = 0 max_sum = -1e9 for i in range(len(numbers)): current_sum += numbers[i] if max_sum < current_sum: max_sum = current_sum if current_sum < numbers[i]: current_sum = numbers[i] print("largest sum is ", max_sum) kadane([-10, 5, 1, 6, -9, 2, -7, 3, -5])
出力：
largest sum is 12
最大和連続部分配列の複雑性分析
単純なアプローチでは、2 つのループを使用してすべての可能なサブ配列の合計を計算し、最大のものを見つけます。これは総当たりアプローチです。各ループは、 配列、与える O(N²) 時間。
カダネのアルゴリズムはループを1つしか使用しないため、処理時間はO(N)、追加メモリはO(1)で済みます。100個の要素を持つ配列の場合、単純な手法では100×100＝10,000回の演算が必要ですが、カダネのアルゴリズムではわずか100回の演算で済みます。これは、入力サイズが大きい場合に劇的な高速化を実現します。
