C++ では、配列のプレフィックスに -1 を乗算して配列の合計を最大化します。

整数の配列があり、タスクはまず配列のプレフィックスを取得し、次にそれに -1 を掛け、次に配列のプレフィックスの合計を計算することです。そして最後に、生成されたプレフィックス配列の最大値を見つけます。

プレフィックス配列は次のように生成されます。

プレフィックス配列の最初の要素 prefixArray[0] = 配列の最初の要素

プレフィックスの 2 番目の要素配列 prefixArray[1] = prefixArray[0] arr[1]

プレフィックス配列の 3 番目の要素 prefixArray[2] = prefixArray[1] arr[2]

プレフィックス配列の 4 番目の要素プレフィックス配列 prefixArray[3] = prefixArray[2] arr[3] ...など。

この問題のさまざまな入出力状況を見てみましょう -

For int arr[] = {2, 4, 1, 5, 2}

出力 プレフィックス配列は次のとおりです: -2 2 3 8 10 配列のプレフィックスに -1 を乗算して配列の合計を最大化します: 21

説明 - 整数の配列があります。まず、配列の接頭辞 (2) を取得し、それに -1 を掛けます。したがって、新しい配列は {-2, 4, 1, 5, 2} になります。ここで、プレフィックス配列の最大合計を形成します。

プレフィックス配列は {-2, 2, 3, 8, 10} です。最後のステップでは、合計を -2 2 3 8 `0 = 21 に最大化します。これが最終出力です。

In- int arr[] = {-1, 4, 2, 1, -9, 6};

出力- プレフィックス配列は次のとおりです: 1 5 7 8 -1 5 配列のプレフィックスに -1 を乗算すると、最大化される配列の合計は次のようになります: 19

説明-整数の配列。まず、配列のプレフィックス -1 を取得し、それに -1 を掛けます。したがって、新しい配列は {1, 4, 2, 1, -9, 6} になります。今、私たちは形成します プレフィックス配列は {1, 5, 7, 8, -1, 5} です。最後のステップでは、合計を 1 5 8 5 = 19 に最大化し、これが最終出力になります。

次のプログラムで使用されるメソッドは次のとおりです。 -

• 整数配列と一時変数 x を -1 として宣言し、arr[0] を次のように設定します。 arr [0]*x。

• 配列のサイズを計算します。プレフィックス配列 prefix_array[size] を宣言します。関数 create_prefix_arr(arr, size, prefix_array) を呼び出して、指定された配列のプレフィックス配列を生成します。プレフィックス配列を出力します。

• 関数 Maximum_sum(prefix_array, size) を呼び出します。この関数は、配列の最大合計を保存します。

• 関数内 void create_prefix_arr(int arr[], int size, int prefix_array[])

  • prefix_array[0] を arr に設定します[0]。

  • i から 0 まで、配列のサイズになるまでループします。ループ内で、prefix_array[i] を prefix_array[i-1] arr[i] に設定します。

• #関数内で int Maximum_sum(int prefix_array[], int size)
  • 一時変数 temp を宣言し、 -1 に設定します。

  • i から 0 まで、配列のサイズになるまでループします。ループ内で、temp を max(temp, prefix_array[i]) に設定します。

  • 配列 arr[temp 1] を宣言し、配列のすべての要素を 0 に初期化します。

  • i から 0 まで、配列のサイズになるまでループします。ループ内で、arr[prefix_array[i]]

  • は一時変数 max_sum を宣言し、0 に設定します。変数 i を temp

  • として宣言し、i>0 のときにループを開始します。 arr[i] > 0 かどうかを確認し、max_sum を max_sum i に設定し、arr[i-1]-- と arr[i]-- を設定します。それ以外の場合は、i を 1 ずつ減らします。

  #max_sum を返します。

例

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//create the prefix array
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
   prefix_array[0] = arr[0];
   for(int i=0; i<size; i++)  {
      prefix_array[i] = prefix_array[i-1] + arr[i];
   }
}
//find the maximum sum of prefix array
int maximize_sum(int prefix_array[], int size) {
   int temp = -1;
   for(int i = 0; i < size; i++) {
      temp = max(temp, prefix_array[i]);
   }
   int arr[temp + 1];
   memset(arr, 0, sizeof(arr));

   for(int i = 0; i < size; i++) {
      arr[prefix_array[i]]++;
   }
   int max_sum = 0;
   int i = temp;
   while(i>0) {
      if(arr[i] > 0) {
         max_sum = max_sum + i;
         arr[i-1]--;
         arr[i]--;
      } else {
         i--;
      }
   }
   return max_sum;
}

int main() {
   int arr[] = {2, 4, 1, 5, 2};
      int x = -1;
      arr[0] = arr[0] * x;
      int size = sizeof(arr) / sizeof(arr[0]);
   int prefix_array[size];

   //call function to create a prefix array
   create_prefix_arr(arr, size, prefix_array);
   //print the prefix array
   cout<<"Prefix array is: ";
   for(int i = 0; i < size; i++) {
      cout << prefix_array[i] << " ";
   }
   //print the maximum sum of prefix array
   cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
   return 0;
}

出力

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

Prefix array is: -2 2 3 8 10
Maximize the sum of array by multiplying prefix of array with -1 are: 21

以上がC++ では、配列のプレフィックスに -1 を乗算して配列の合計を最大化します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。