In C++, maximize the sum of an array by multiplying its prefix by -1

We have an array of integers, and the task is to first get the prefix of the array, then multiply it by -1, secondly calculate the sum of the prefixes of the array, and finally find the maximum in the generated prefix array and.

The prefix array is generated as follows:

The first element of the prefix array prefixArray[0] = the first element of the array

The second element of the prefix array prefixArray[ 1] = prefixArray[0] arr[1]

The third element of the prefix array prefixArray[2] = prefixArray[1] arr[2]

The fourth element of the prefix array prefixArray[3] = prefixArray[2] arr[3] ...and so on.

Let's look at the various input and output situations of this problem -

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

Output The prefix array is: -2 2 3 8 10 Maximize the sum of the array by multiplying the prefix of the array by -1: 21

Explanation - We have an array of integers. First we get the prefix of the array, which is 2, and multiply it by -1. So, the new array is {-2, 4, 1, 5, 2}. Now, we will form the maximum sum of the prefix array.

The prefix array is {-2, 2, 3, 8, 10}. The last step is to maximize the sum to -2 2 3 8 `0 = 21, which is the final output.

In- int arr[] = {-1, 4, 2, 1, -9, 6};

Output- prefix The array is: 1 5 7 8 -1 5 By multiplying the prefix of the array with -1, the sum of the array that is maximized is: 19

Explanation- We have an array of integers. First we take the prefix of the array -1 and multiply it by -1. So, the new array will be {1, 4, 2, 1, -9, 6}. Now we will form The prefix array is {1, 5, 7, 8, -1, 5}. The final step is to maximize the sum to 1 5 8 5 = 19, which is the final output.

The method used in the following program is as follows −

• Declare an integer array and a temporary variable x as -1, and then set arr[0] to arr [0]*x.

• Calculate the size of the array. Declare a prefix array prefix_array[size]. Call the function create_prefix_arr(arr, size, prefix_array) to generate a prefix array for the given array. Print the prefix array

• Call the function maximize_sum(prefix_array, size), which will store the maximum sum of the array.

• In the function void create_prefix_arr(int arr[], int size, int prefix_array[])

  • Set prefix_array[0] to arr[0].

  • Loop from i to 0 until the size of the array. Inside the loop, set prefix_array[i] to prefix_array[i-1] arr[i].

• Inside the function int maximize_sum(int prefix_array[], int size)

  • Declare a temporary variable temp and Set it to -1.

  • Loop from i to 0 until the size of the array. Inside the loop, set temp to max(temp, prefix_array[i])

  • Declare an array arr[temp 1] and initialize all elements of the array to 0.

  • Loop from i to 0 until the size of the array. Inside the loop, arr[prefix_array[i]]

  • declares a temporary variable max_sum and sets it to 0. Declare a variable i as temp

  • and start the loop when i>0. Check if arr[i] > 0, then set max_sum to max_sum i, and set arr[i-1]-- and arr[i]--. Otherwise, decrement i by 1.

  • Return max_sum.

Example

#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;
}

Output

If we run the above code, the following output will be generated

Prefix array is: -2 2 3 8 10
Maximize the sum of array by multiplying prefix of array with -1 are: 21

The above is the detailed content of In C++, maximize the sum of an array by multiplying its prefix by -1. For more information, please follow other related articles on the PHP Chinese website!