我们有一个整数数组，任务是首先获取数组的前缀，然后将其乘以-1，其次计算数组的前缀和，最后找到生成的前缀数组中的最大和。
前缀数组生成如下：
前缀数组的第一个元素prefixArray[0] = 数组的第一个元素
前缀数组的第二个元素prefixArray[1] = prefixArray[0] + arr[1]
前缀数组的第三个元素prefixArray[2] = prefixArray[1] + arr[2]
立即学习“C++免费学习笔记（深入）”；
前缀数组的第四个元素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 using namespace std;#define Max_size 5//create the prefix arrayvoid create_prefix_arr(int arr[], int size, int prefix_array[]) { prefix_array[0] = arr[0]; for(int i=0; i0) { 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: -2 2 3 8 10Maximize the sum of array by multiplying prefix of array with -1 are: 21
登录后复制
以上就是在C++中，通过将数组的前缀与-1相乘来最大化数组的和的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2582930.html
