C ++でサブアレイのすべての要素にXを掛けた後、サブアレイの合計を最大化します

整数配列と整数変数、つまり「X」が与えられます。タスクは、最初に指定された配列からサブ配列を形成し、次にサブ配列のすべての要素に整数Xを乗算することです。最後に、最大合計に寄与する要素を見つけます。

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

で − int arr [] ={2、4、1、-5、-2}、X =3

アウト −サブアレイのすべての要素にXを掛けた後、サブアレイの合計を最大化します。21

説明 − Xとして配列と整数変数が与えられます。最初に、与えられた配列からサブ配列をフェッチします。たとえば、{2、4、1}とします。次に、サブ配列のすべての要素にX、つまり3を掛けて、配列が{6、12、3、-5、-2}になるようにします。最後に、6 + 12 + 3=21によって返されるサブアレイの最大合計を確認します。

で − int arr [] ={-1、2、-6、3、-4}、x =-1

アウト −サブアレイのすべての要素にXを掛けた後、サブアレイの合計を最大化します。11

説明 − Xとして配列と整数変数が与えられます。最初に、与えられた配列からサブ配列をフェッチします。たとえば、{-1、-6、-4}とします。次に、サブ配列のすべての要素にX、つまり-1を掛けて、配列が{1、2、6、3、4}になるようにします。最後に、1 + 6 + 4=11によって返されるサブアレイの最大合計を確認します。

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

• 整数配列と整数変数を「X」として入力します。配列のサイズを計算し、そのデータを関数Max_Subarray（arr、size、x）に渡します。

• 関数Max_Subarray（arr、size、x）

  の内部

  • 配列をintarr_2[size] [3]として宣言し、一時変数をtempとして0として宣言します。

  • C ++でmemset（）メソッドを使用して、配列「arr_2」のすべての要素を-1で初期化します。

  • 配列のサイズまで、iから0までのループFORを開始します。ループ内で、関数max（temp、check（i、0、arr、arr_2、size、x））

    の呼び出しにtempを設定します。

  • 戻り温度。

• 関数内intcheck（int first、int last、int arr []、int arr_2 [Max_size] [3]、int size、int x）

  • 一時変数をカウントとして0として宣言します。

  • 最初にIFをチェック=サイズ、次に0を返します

  • IF arr_2 [first] [last]！=-1を確認してから、arr_2[first][last]を返します。

  • IF last =0をチェックしてから、C ++の組み込みmax関数を呼び出して、最大値をmax（count、arr [first] + check（first + 1、0、arr、arr_2、size、x））として見つけ、カウントを設定します=max（count、x * arr [first] + check（first + 1、1、arr、arr_2、size、x））

  • ELSE IF check last =1次に、countをmax（count、x * arr [first] + check（first + 1、1、arr、arr_2、size、x））に設定し、countをmax（count、arr[first]]に設定します。 +チェック（最初の+ 1、2、arr、arr_2、サイズ、x））

  • ELSE、カウントをmax（count、arr [first] + check（first + 1、2、arr、arr_2、size、x））;

    に設定します。

  • arr_2[first][last]を返してカウントします。

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5

int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
   int count = 0;
      if(first == size){
         return 0;
      }
      if(arr_2[first][last] != -1){
         return arr_2[first][last];}
      if (last == 0){
         count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
         count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
      }
      else if(last == 1){
         count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
         count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
      }
      else{
         count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
      }
      return arr_2[first][last] = count;
}
int Max_Subarray(int arr[], int size, int x){
   int arr_2[size][3];
   int temp = 0;
   memset(arr_2, -1, sizeof arr_2);
   for(int i = 0; i < size; i++){
      temp = max(temp, check(i, 0, arr, arr_2, size, x));
   }
   return temp;
}
int main(){
   int arr[] = {2, 4, 1, -5, -2};
   int size = sizeof(arr) / sizeof(arr[0]);
   int x = 3;
   cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
   return 0;
}

出力

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

Maximize the subarray sum after multiplying all elements of any subarray with X are: 21