数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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}。现在，我们将形成前缀数组 {-2, 2, 3, 8, 10}。最后一步是最大化和，即 -2 + 2 + 3 + 8 + 10 = 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 + 7 + 8 + 5 = 26，这是最终输出。(原文计算错误，应为26)
下面程序中使用的方法如下：
声明一个整数数组和一个临时变量 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` 开始循环到数组大小。在循环内，将 `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。声明一个变量 `int i = temp`。
开始 `WHILE i > 0` 循环。检查 `IF 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
231 次浏览
