数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中利用给定操作最大化数组和
描述
有一个包含(2 * n – 1)个整数的数组。我们可以改变数组中恰好n个元素的符号。换句话说，我们可以选择恰好n个数组元素，并将它们分别乘以-1。求数组的最大和。
示例
如果输入数组是{-2, 100, -3}，那么我们可以通过改变-2和-3的符号来获得最大值。改变符号后，数组变为：
{2, 100, 3}，这个数组的最大和是105。
算法
- 计算负数个数
- 通过取数字的绝对值来计算数组的和。
- 通过取数字的绝对值来查找数组中的最小数字
- 检查负数个数是否为奇数且n的值为偶数，如果是，则从总和中减去两倍的m，这将是数组的最大和；否则，总和的值将是数组的最大和
- 重复上述步骤 (2 * n – 1) 次
示例
让我们来看一个例子：
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int *arr, int n) {
int negtiveCnt = 0;
int sum = 0;
int m = INT_MAX;
for (int i = 0; i < 2 * n - 1; ++i) {
if (arr[i] < 0) {
++negtiveCnt;
}
sum = sum + abs(arr[i]);
m = min(m, abs(arr[i]));
}
if (negtiveCnt % 2 && n % 2 == 0) {
sum = sum - 2 * m;
return sum;
}
return sum;
}
int main() {
int arr[] = {-2, 100, -3};
int n = 2;
cout << "Maximum sum = " << getMaxSum(arr, n) << endl;
return 0;
}输出
Maximum sum = 105
更新于：2019-12-31
130 次浏览
广告