整数の配列があり、タスクはまず配列のプレフィックスを取得し、次にそれに -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] に設定します。
#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 サイトの他の関連記事を参照してください。