首页  >  文章  >  后端开发  >  在C++中,通过将数组的前缀与-1相乘来最大化数组的和

在C++中,通过将数组的前缀与-1相乘来最大化数组的和

WBOY
WBOY转载
2023-09-08 15:17:02726浏览

在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中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除