在 C++ 中通过将数组的前缀乘以 -1 来最大化数组的总和
给定一个整数数组，任务是先获取数组的前缀，然后乘以-1，然后计算数组的前缀和，最后从生成的前缀数组中找到最大和。
前缀数组生成为-
prefixArray[0]的第一个元素=数组的第一个元素
prefixArray[1]的第二个元素=prefixArray[0]+arr[1]
prefixArray[2]的第三个元素=prefixArray[1]+arr[2]
prefixArray[3]的第四个元素=prefixArray[2]+arr[3].....等。
让我们看看这个的各种输入输出场景-
在- intarr[]={2,4,1,5,2}
Out-前缀数组是：-223810通过将数组的前缀乘以-1来最大化数组的总和是：21
说明 -我们给出了一个整数数组。因此，我们将首先获取数组的前缀2并将其与-1相乘。因此，新数组将是{-2,4,1,5,2}。现在，我们将形成前缀数组{-2,2,3,8,10}。最后一步是将总和最大化为-2+2+3+8+`0=21，即最终输出。
在 -intarr[]={-1,4,2,1,-9,6};
Out −前缀数组为：1578-15通过将数组的前缀乘以-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_arry[size]。调用函数create_prefix_arr(arr,size,prefix_array)以从给定数组生成前缀数组。打印前缀数组
调用maximize_sum(prefix_array,size)将存储数组最大和的函数。
在函数内部voidcreate_prefix_arr(intarr[],intsize,intprefix_array[])
将prefix_array[0]设置为arr[0]。
从i到0开始循环FOR直到数组的大小。在循环内，将prefix_array[i]设置为prefix_array[i-1]+arr[i]。
在函数内部intmaximize_sum(intprefix_array[],intsize)
将临时变量声明为temp并将其设置为-1。
从i到0开始循环FOR直到数组的大小。在循环内，将temp设置为max(temp,prefix_array[i])
将数组声明为arr[temp+1]并用0初始化数组的所有元素。
从i到0开始循环FOR直到数组的大小。在循环内，设置arr[prefix_array[i]]++
将临时变量声明为max_sum并将其设置为0。将变量声明为inti到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
//创建前缀数组
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];
}
}
//找到前缀数组的最大和
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];
//调用函数来创建前缀数组
create_prefix_arr(arr, size, prefix_array);
//打印前缀数组
cout<<"前缀数组是： ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//打印前缀数组的最大和
cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
前缀数组是： -2 2 3 8 10 Maximize the sum of array by multiplying prefix of array with -1 are: 21