Kadence のアルゴリズム: 最大合計連続サブ配列
サラ・チェン
連続する部分配列の合計の最大値は何ですか?
サブ配列は配列の連続した部分です。 配列の単一要素または配列の一部を指定できます。 最大和連続部分配列とは、最大和値を持つ部分配列を意味します。
たとえば、配列は {-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} = 11 は、上記の配列の部分配列の可能なすべての組み合わせにおける最大合計です。 したがって、上記の配列の場合、最大の部分配列は {5,1,6} です。
Kadence のアルゴリズム: 最大合計連続サブ配列
連続部分配列の最大合計を解く簡単なアプローチ
この問題を解決する簡単な方法は、XNUMX つのループを使用してすべての部分配列を見つけ、合計を計算し、その最大値を見つけることです。
以下は、連続するサブ配列の合計の最大値を見つけるための簡単なアプローチのフローチャートです。 考えられるすべてのサブ配列を調べているため、これは総当り的なアプローチです。
これを行うための簡単な手順を次に示します。
ステップ1） max_sum を最小の整数値で初期化し、変数「begin」と「end」にゼロを割り当てます。
ステップ2） i と j を配列のインデックスとします。ここで、「j」は「i」以上です。 これはサブ配列の開始インデックスを表し、「j」はサブ配列の終了インデックスを表します。
ステップ3） 「Current_sum」は部分配列の合計を保持します。 現在の合計を計算した後、current_sum が max_sum より大きいかどうかを確認します。
ステップ4） current_sum の方が大きい場合は、max_sum を現在の合計に置き換えます。
ステップ5） 「j」が配列の末尾に達しているかどうかを確認します。 「j」が配列の最後に達した場合、「i」をインクリメントし、current_sum の値を 0 に変更します。
ステップ6） 「i」が配列の最後に達するまで、これらすべての手順を実行します。
ステップ7） これら XNUMX つのループの最後で、max_sum には最大の部分配列の合計が保持されます。
シンプルなアプローチのための疑似コード
function maximumSubarraySum():
input: array
for all possible subArray from array:
calculate sum of each sub array
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
最大合計の連続部分配列を見つけるための Kadane のアルゴリズム
Kadane のアルゴリズムは、「動的計画法」手法の一種です。 ここでは、XNUMX つのループの代わりに XNUMX つのループを使用します。 Kadane のアルゴリズムの一般的な実装は、正の数の配列に対してのみ機能します。
合計の最大の連続部分配列を見つけるために必要な変数は XNUMX つだけです。 Kadane のアルゴリズムのフローチャートは次のとおりです。
Kadane のアルゴリズムの手順は次のとおりです。
ステップ1） current_sum と max_sum という XNUMX つの変数を作成します。
「Current_sum」は特定の配列インデックスで終わる最大合計値を保持し、「max_sum」はこれまでの最大合計値を保存します。
ステップ2） 各配列要素の current_sum に値を追加します。 次に、以下の XNUMX つの条件を確認します。
- current_sum が現在の要素より小さい場合、current_sum の値が現在の要素になります。
- max_sum が current_sum より小さい場合、max_sum は current_sum になります。
ステップ3） 配列全体に対して前のステップを実行すると、「max_sum」変数に最大合計の連続サブ配列が得られます。
Kadane のアルゴリズムの例
小さなサイズの配列を使用して Kadanes のアルゴリズムを実証し、最大合計の連続部分配列を見つける各ステップについて説明します。
与えられた配列が次のようなものであると仮定します。
Kadane のアルゴリズムの手順は次のとおりです。
ステップ1） current_sum と max_sum という XNUMX つの変数を作成します。 INT_MIN を max_sum に割り当て、ゼロを current_sum に割り当てます。 (ここで、INT_MIN は最小の整数を意味します)。
ステップ2） インデックス 0 の値は 4 です。したがって、current_sum = 0 + 4 または 4 となります。ここで、current_sum が max_sum より大きい場合、max_sum は 4 になります。
ステップ3） インデックス 1 の値は -2 です。 したがって、current_sum = 4 + (-2) または 2 となります。
今回は、current_sum が max_sum よりも小さくなります。 その結果、max_sum の値は更新されません。
ステップ4） 次の値は 1 です。これを current_sum と加算すると、current_sum は 3 になります。それでも、max_sum は current_sum より大きくなります。 したがって、max_sum は更新されません。
ステップ5） インデックス 3 の値は 3 です。 current_sum を 6 ずつ増分して値を更新します。つまり、current_sum は XNUMX になります。
この場合、max_sum は current_sum より小さくなります。 したがって、max_sum は current_sum の値で更新されます。
ステップ6） 配列の最後の要素には -1 を付けます。 これを current_sum と加算すると、current_sum は 5 となり、max_sum よりも小さくなります。 したがって、max_sum は 6 のままになります。
配列の最後に到達したため、アルゴリズムはここで終了します。 ここで、「max_sum」には最大合計サブ配列が含まれます。 これは 5 です。部分配列は {4,-2,1,3} です。
Kadane のアルゴリズムの疑似コード
function KadaneAlgorithm():
input: array
maximum_sum, current_sum = 0
for each elements 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 -10000000
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
最大和連続部分配列の複雑性分析
シンプルなアプローチでは XNUMX つのループを使用します。 このメソッドは、考えられるすべての部分配列の合計を計算して、最大のものを見つけます。 それは強引なアプローチです。 各ループは終了するまで実行されます。 配列.
配列の合計が次の場合 N 要素を分割し、XNUMX つのループを使用して N 個の要素を処理します。2 結果として、連続する部分配列の最大和を求める単純なアプローチの時間計算量は、 O(N2). ここで、「O」は複雑度関数を意味します。
一方、Kadane のアルゴリズムは、最大の連続合計部分配列を見つける動的計画法です。 例またはコードに従ってみると、ループが XNUMX つだけ使用されていることがわかります。
その結果、入力配列のサイズが Nの場合、Kadane アルゴリズムの時間計算量は O(N) になります。これは、単純なアプローチよりも高速です。たとえば、100 個の要素を含む配列の場合、単純なアプローチでは 100*100 または 10,000 CPU 時間かかります。しかし、Kadane アルゴリズムでは 100 CPU 時間しかかかりません。
