C++の特定の範囲での最大サブアレイ合計

任意のサイズの整数要素の配列が与えられます。タスクは、配列内の任意の可能なインデックス値から開始できる、指定された範囲内の指定された配列からサブ配列を形成することによって計算される最大合計を見つけることです。

このためのさまざまな入出力シナリオを見てみましょう-

で − int arr [] ={3、2、-1、6、7、2}、int first =0、int last =5

アウト −指定された範囲の最大サブアレイ合計は次のとおりです：19

説明 −正の値と負の値の両方を含む配列と、0から5までの範囲、つまり配列のすべてのインデックスをカバーする配列が与えられます。したがって、合計が最大のサブアレイは3 + 6 + 7 + 2 + 2-1、つまり19になります。

で − int arr [] ={-2、1、3、4、8、9、23}、int first =0、int last =3

アウト −指定された範囲の最大サブアレイ合計は次のとおりです：8

説明 −正の値と負の値の両方を含む配列と、0から3までの範囲、つまり配列の0から3のインデックスをカバーする範囲が与えられます。したがって、合計が最大のサブ配列は1 + 3 + 4、つまり8になります。

以下のプログラムで使用されているアプローチは次のとおりです

• max_val、max_temp、total、sub_sumをメンバー変数として格納し、デフォルトのコンストラクターを使用してmax_val、max_temp、sum_sum、およびtotalを最大値として設定するツリーの構造を構築します。

• max_valをmax（left.max_val、left.total + right.max_val）、max_tempをmax（right.max_temp、right.total + left.max_temp）、total asとして設定することにより、ツリーを形成する構造体のメソッドをset_nodeとして作成します。 left.total+right.totalおよびsub_sumasmax（{left.sub_sum、right.sub_sum、left.max_temp + right.max_val}）次に、ノードを返します。

• ツリーの構築に使用されるbuild_treeとしてメソッドを作成します。

  • IF first =lastをチェックしてから、total、max_temp、max_val、sub_sumをarr[first]として設定して返します。

  • build_tree（node、arr、first、temp、2 * inx）およびbuild_tree（node、arr、temp + 1、last、2 * inx + 1）としてbuild_treeメソッドを呼び出し、node [inx]をset_nodes（ node [2 * inx]、node [2 * inx + 1]）

• create_treeとしてメソッドを作成し、tempを（int）（ceil（log2（size）））として設定してから、ツリーのノードオブジェクト、arr、値0、配列のサイズ-1を渡してbuild_tree（）メソッドを呼び出します。引数として値1。

• 最大サブ配列の合計をmaximum_sub（Tree * node、int temp、int temp_2、int temp_3、int temp_4、int inx）として見つけるメソッドを作成します

  • temp_4より大きいかtemp_2がtemp_3より小さいかどうかを確認し、NULLを返します

  • temp_3よりも大きい温度とtemp_4よりも小さいtemp_2の場合を確認してから、node [inx]

    を返します。

  • 左のメソッドを呼び出して関数maximum_sub（node、temp、mid、temp_3、temp_4、2 * inx）を呼び出し、右のメソッドをmaximum_sub（node、mid + 1、temp_2、temp_3、temp_4、2 * inx + 1 ）

  • 結果をset_nodes（left、right）

    として設定します

  • 結果を返します。

• maximum_subarray（Tree * node、int first、int last、int size）としてメソッドを作成します

  • maximum_sub（node、0、size -1、first、last、1）

    としてメソッドの呼び出しを作成します

  • temp.sub_sumを返す

• main（）関数内

  • 正の値と負の値を持つ整数型の配列を宣言し、配列のサイズを計算します。

  • 最初のインデックスから最後のインデックスまでの範囲を定義します。

  • 関数maximum_subarray（node、first、last、size）を呼び出して、指定された範囲の最大サブアレイ合計を計算します

例

#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
struct Tree{
   int max_val;
   int max_temp;
   int total;
   int sub_sum;
   Tree(){
      max_val = max_temp = sub_sum = -MAX;
      total = -MAX;
   }
};

Tree set_nodes(Tree left, Tree right){
   Tree node;
   node.max_val = max(left.max_val, left.total + right.max_val);
   node.max_temp = max(right.max_temp, right.total + left.max_temp);
   node.total = left.total + right.total;
   node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
   return node;
}
void build_tree(Tree* node, int arr[], int first, int last, int inx){
   if(first == last){
      node[inx].total = arr[first];
      node[inx].max_temp = arr[first];
      node[inx].max_val = arr[first];
      node[inx].sub_sum = arr[first];
      return;
   }
   int temp = (first + last) / 2;
   build_tree(node, arr, first, temp, 2 * inx);
   build_tree(node, arr, temp + 1, last, 2 * inx + 1);
   node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}
Tree* create_tree(int arr[], int size){
   int temp = (int)(ceil(log2(size)));
   int n = 2 * (int)pow(2, temp) - 1;
   Tree* node = new Tree[n];
   build_tree(node, arr, 0, size - 1, 1);
   return node;
}
Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx){
   if(temp > temp_4 || temp_2 < temp_3){
      Tree nullNode;
      return nullNode;
   }
   if(temp >= temp_3 && temp_2 <= temp_4){
      return node[inx];
   }
   int mid = (temp + temp_2) / 2;
   Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
   Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
   Tree result = set_nodes(left, right);
   return result;
}
int maximum_subarray(Tree* node, int first, int last, int size){
   Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
   return temp.sub_sum;
}
int main(){
   int arr[] = { 3, 2, -1, 6, 7, 2 };
   int size = sizeof(arr) / sizeof(arr[0]);
   Tree* node = create_tree(arr, size);
   int first = 0;
   int last = 5;
   int sub_sum = maximum_subarray(node, first, last, size);
   cout<< "Maximum Subarray Sum in a given Range is: "<< sub_sum;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Maximum Subarray Sum in a given Range is: 19