给定一个整数数组，任务是先获取数组的前缀，然后乘以-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}
Out - 前缀数组是：-2 2 3 8 10 通过将数组的前缀乘以 -1 来最大化数组的总和是：21
说明 - 我们给出了一个整数数组。因此，我们将首先获取数组的前缀 2 并将其与 -1 相乘。因此，新数组将是 {-2, 4, 1, 5, 2}。现在，我们将形成前缀数组 {-2, 2, 3, 8, 10}。最后一步是将总和最大化为 -2+2+3+8+`0 = 21，即最终输出。
在 - int arr[] = {-1, 4, 2, 1, -9, 6};
Out − 前缀数组为：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_arry[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 开始循环 FOR 直到数组的大小。在循环内，将 prefix_array[i] 设置为 prefix_array[i-1] + arr[i]。
在函数内部 int maximize_sum(int prefix_array[], int size)
将临时变量声明为 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。将变量声明为 int 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
//创建前缀数组
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