C++での最大循環サブ配列の合計

配列が与えられ、タスクは、サブ配列の合計が循環的に最大値になるようにサブ配列を形成することです。

入力 − int arr [] ={1、2、8、4、3、0、7}

出力 −最大循環サブアレイの合計は− 22

説明 − {1、2、8、4、3、0、7}を含む配列が与えられ、そのサブ配列の合計は7 + 1 + 2+ 8+4は22になります。

入力 − int arr [] ={2、5、-1、6、9、4、-5}

出力 −最大循環サブアレイの合計は− 25

説明 − {2、5、-1、6、9、4、-5}を含む配列が与えられ、合計が最大のそのサブ配列は4 + 2 + 5 --1 + 6+9は25になります。

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

• 正の値と負の値の両方を含む整数要素の配列を入力します。

• 配列のサイズを計算します。

• 配列とサイズを関数に渡して、さらに処理します。

• 一時変数を合計として作成し、0に設定します

• 配列のサイズまでiから0までのループFORを開始します

• ループ内で、合計+ arr [i]

  で合計を設定します

• temp =arr [0]、temp_2 =arr [0]、temp_3 =arr [0]、temp_4 =arr [0]

  に設定します

• 配列のサイズまでiから1までのループFORを開始します

• ループ内セットtemp=max（temp + arr [i]、arr [i]）、temp_2 =max（temp_2、temp）、temp_3 =min（temp_3 + arr [i]、arr [i]）、temp_4 =min （temp_4、temp_3）

• IFサイズ==1を確認してから、arr [0]

  を返します。

• IF temp_4 ==totalを確認してから、temp_2を返します

• max_sum =max（temp_3、total --temp_4）

  を設定します

• max_sumを返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
   int total = 0;
   for (int i = 0; i < size; i++){
      total += arr[i];
   }
   int temp = arr[0];
   int temp_2 = arr[0];
   int temp_3 = arr[0];
   int temp_4 = arr[0];
   for (int i = 1; i < size; i++){
      temp = max(temp + arr[i], arr[i]);
      temp_2 = max(temp_2, temp);
      temp_3 = min(temp_3 + arr[i], arr[i]);
      temp_4 = min(temp_4, temp_3);
   }
   if (size == 1){
      return arr[0];
   }
   if (temp_4 == total){
      return temp_2;
   }
   int max_sum = max(temp_3, total - temp_4);
   return max_sum;
}
int main(){
   int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
   return 0;
}

出力

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

Maximum circular subarray sum is: 25