C++ 通过用另一个数组的元素替换数组元素的和或与元素的乘积来最大化数组的乘积

给定两个长度相同的数组，我们必须应用一些操作来使第一个数组乘以所有元素最大。操作是将第二个数组的任意元素乘以第一个数组的任意元素，只能乘或加一次。我们可以将第二个数组的两个不同元素乘以单个第一个数组的元素。在所有操作之后，我们必须将第一个数组中所有元素的乘积返回。

例子

让我们通过一个例子来理解问题－

输入

int arr[] = {2, 1, 3};
int brr[] = {3, 2, 4};

输出

216

解释

首先，我们将第二个数组中的2加到第一个数组的1上，它将变为3，然后我们将3乘以2，它将变为6。最后，我们将4乘以3，它将变为12。所以最终的数组将是6、12和3。

方法

首先，让我们看一下优先队列数据结构 –

优先队列是C++ STL中定义的基于堆的数据结构。它有两个版本，其中一个版本将最大或最小的元素存储在顶部。我们使用的版本将最小元素存储在顶部，并且其语法是 –

priority_queue<data_type, vector<data_type>, greater<data_type>> priority_queue_name;

在这里，data_type是我们需要存储在优先队列中的数据类型，例如int、long long、float、vector等，priority_queue_name是我们给予优先队列的名称。

让我们来看一下实现所需的步骤：

• 首先，我们需要创建一个函数，该函数将以给定的两个数组和它们的长度作为参数，并返回一个整数值，该值为答案。

• 在函数中，首先，我们将创建一个优先队列，并使用for循环将第一个数组的所有元素添加到优先队列中。

• 之后，我们将对第二个数组进行排序，然后遍历它。

• 在每次迭代中，我们将获取优先队列的顶部元素，该元素将是给定的第一个数组中的最小元素。

• 我们的目标是获取最小元素并对最小元素进行操作，使其变大，因为我们的目标是尽可能将最小元素变得最大。

• 我们将遍历数组，并在每次迭代中弹出最小元素，并在其上进行一个操作，该操作可以是乘法或加法，根据哪个操作会产生更大的结果，然后将其添加到优先队列中。

• 最后，我们将遍历优先队列并将所有元素的乘积返回给主函数，然后我们将在主函数中打印它。

示例

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

// function to get the result 
int getProduct(int arr[], int brr[], int n){
   // create a priority queue. It will store the elements in decreasing order 
   priority_queue<int, vector<int>, greater<int>> pq;    
   // traversing over the first array to add all the elements to the priority queue 
   for(int i=0; i<n; i++){
      pq.push(arr[i]);
   }    
   // sorting the second array 
   sort(brr, brr + n);    
   // traversing over the second array to multiply its elements 
   for(int i=0; i<n; i++){
      int cur = pq.top(); // smallest element of first array
      // pop it out 
      pq.pop();        
      // apply operation on it 
      cur = max(cur * brr[i], cur + brr[i]);
      // again add it to queue 
      pq.push(cur);
   }    
   // traverse over the  priority queue to get the answer 
   int ans = 1; // variable to store the answer    
   for(int i=0; i<n; i++){
      ans *= pq.top();
      pq.pop();
   }    
   // return final answer
   return ans;
}
int main(){
   // defining the given arrays 
   int arr[] = {2, 1, 3};
   int brr[] = {3, 2, 4};    
   int n = 3; // size of the given arrays     
   cout<<"The maximum product of the array elements after operations is: "<<getProduct(arr, brr, n)<<endl;
   return 0; 
}

输出

The maximum product of the array elements after operations is: 216

时间和空间复杂度

上述代码的时间复杂度是O(N*log(N))，其中N是给定数组的大小，由于使用了优先队列，我们得到了对数因子。

上述代码的空间复杂度是O(N)，因为我们使用了额外的空间来存储优先队列。

总结

在本教程中，我们通过对给定数组应用一些给定操作来找到最大乘积的程序。我们从第二个给定数组中选择一些元素，并将它们与第一个数组的元素相乘或相加。我们使用了一个优先队列的程序，在O(N*log(N))的时间和O(N)的额外空间下实现。