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} をシーケンスを維持していないため、サブ配列になります。

最大合計連続サブアレイ

すべてのサブ配列の中で、次のようになります。wing 強調表示された部分配列 (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 のアルゴリズム

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 のアルゴリズムを実証し、最大合計の連続部分配列を見つける各ステップについて説明します。

与えられた配列が次のようなものであると仮定しましょうwing:

Kadane のアルゴリズムの例

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 になります。

Kadane のアルゴリズムの例

ステップ3) インデックス 1 の値は -2 です。 したがって、current_sum = 4 + (-2) または 2 となります。

今回は、current_sum が max_sum よりも小さくなります。 その結果、max_sum の値は更新されません。

Kadane のアルゴリズムの例

ステップ4) 次の値は 1 です。これを current_sum と加算すると、current_sum は 3 になります。それでも、max_sum は current_sum より大きくなります。 したがって、max_sum は更新されません。

Kadane のアルゴリズムの例

ステップ5) インデックス 3 の値は 3 です。 current_sum を 6 ずつ増分して値を更新します。つまり、current_sum は XNUMX になります。

Kadane のアルゴリズムの例

この場合、max_sum は current_sum より小さくなります。 したがって、max_sum は current_sum の値で更新されます。

ステップ6) 配列の最後の要素には -1 を付けます。 これを current_sum と加算すると、current_sum は 5 となり、max_sum よりも小さくなります。 したがって、max_sum は 6 のままになります。

Kadane のアルゴリズムの例

配列の最後に到達したため、アルゴリズムはここで終了します。 ここで、「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

Kadane のアルゴリズムの C++ 実装

#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

Kadane のアルゴリズムの Python 実装

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

とplex連続するサブ配列の最大合計値の解析

シンプルなアプローチでは XNUMX つのループを使用します。 このメソッドは、考えられるすべての部分配列の合計を計算して、最大のものを見つけます。 それは強引なアプローチです。 各ループは終了するまで実行されます。 配列.

配列の合計が次の場合 N 要素を分割し、XNUMX つのループを使用して N 個の要素を処理します。2 要素。 その結果、タイムコムはplex連続する部分配列の合計の最大値を見つける簡単なアプローチは次のようになります。 O(N2). ここで、「O」はコムを意味します。plexシティ機能。

一方、Kadane のアルゴリズムは、最大の連続合計部分配列を見つける動的計画法です。 例またはコードに従ってみると、ループが XNUMX つだけ使用されていることがわかります。

その結果、入力配列のサイズが N、その後タイムコムplexKadane のアルゴリズムの数は O(N) になります。 これは単純なアプローチよりも高速です。 たとえば、100 個の要素を含む配列です。 単純なアプローチでは、100*100、つまり 10,000 の CPU 時間がかかります。 しかし、Kadane のアルゴリズムに必要な CPU 時間はわずか 100 です。