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

整数配列が与えられ、タスクは最初に配列のプレフィックスをフェッチし、次にそれを-1で乗算し、次にアレイのプレフィックス合計を計算し、最後に生成されたプレフィックス配列から最大合計を見つけることです。

プレフィックス配列は-

prefixArray[0]の最初の要素=配列の最初の要素

prefixArray[1]の2番目の要素=prefixArray[0] + arr [1]

prefixArray[2]の3番目の要素=prefixArray[1] + arr [2]

prefixArray[3]の4番目の要素=prefixArray[2] +arr[3]…..etc。

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

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

アウト −プレフィックス配列は次のとおりです。-22 3 8 10配列のプレフィックスに-1を掛けて、配列の合計を最大化します。21

説明 −整数配列が与えられます。したがって、最初に2である配列のプレフィックスをフェッチし、それを-1で乗算します。したがって、新しい配列は{-2、4、1、5、2}になります。ここで、{-2、2、3、8、10}のプレフィックス配列を作成します。最後のステップは、合計を-2 + 2 + 3 + 8 + `0=21として最大化することです。これが最終出力です。

で − int arr [] ={-1、4、2、1、-9、6};

アウト −プレフィックス配列は次のとおりです。15 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_arry[size]として宣言します。関数create_prefix_arr（arr、size、prefix_array）を呼び出して、指定された配列からプレフィックス配列を生成します。プレフィックス配列を出力する

• 配列の最大合計を格納する関数maximize_sum（prefix_array、size）を呼び出します。

• 関数内voidcreate_prefix_arr（int arr []、int size、int prefix_array []）

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

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

• 関数内intmaximize_sum（int prefix_array []、int size）

  • 一時変数をtempとして宣言し、-1に設定します。

  • 配列のサイズまで、iから0までのループFORを開始します。ループ内で、tempをmax（temp、prefix_array [i]）

    として設定します。

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

  • 配列のサイズまで、iから0までのループFORを開始します。ループ内で、arr [prefix_array [i]] ++

    を設定します

  • 一時変数をmax_sumとして宣言し、それを0に設定します。変数をintiとしてtempに宣言します

  • i>0の間にループを開始します。 IF 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