在C++中，透過將數組的前綴與-1相乘來最大化數組的和

我們有一個整數數組，任務是先取得數組的前綴，然後將其乘以-1，其次計算數組的前綴和，最後找到生成的前綴數組中的最大和。

前綴數組產生如下：

前綴數組的第一個元素prefixArray[0] = 數組的第一個元素

前綴數組的第二個元素prefixArray[ 1] = prefixArray[0] arr[1]

前綴數組的第三個元素prefixArray[2] = prefixArray[1] arr[2]

#前綴數組的第四個元素prefixArray[3] = prefixArray[2] arr[3] ...等等。

讓我們來看看這個問題的各種輸入輸出情況-

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

輸出 前綴數組為：-2 2 3 8 10 透過將陣列的前綴乘以-1來最大化數組的和：21

解釋 - 我們有一個整數陣列。首先我們取得數組的前綴，即2，並將其乘以-1。所以，新數組為{-2, 4, 1, 5, 2}。現在，我們將形成前綴數組的最大和。

prefix數組為{-2, 2, 3, 8, 10}。最後一步是將和最大化為-2 2 3 8 `0 = 21，這是最終輸出。

在- 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)來產生給定數組的前綴數組。列印前綴數組

• 呼叫函數maximize_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 maximize_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中文網其他相關文章！