数据结构
网络
关系型数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序中的最大权重差
在这个问题中，我们给定一个数组arr[]和一个数字M。我们的任务是创建一个C++程序来计算最大权重差。
问题描述
We will find M elements from the array such that the absolute difference between the sum and the sum of the rest elements is maximum.
让我们通过一个例子来理解这个问题：
输入
arr[] = {3, 1, 6, 9, 4} M = 3输出
15
解释
我们将考虑4,6,9。它们的和是19。与其余数字之和的绝对差是
|19 − 4| = 15
解决方案方法
一个简单的解决方案是找到数组的所有子序列，找到子数组元素的和以及其余元素的和，然后返回最大差值。
一个更高效的解决方案是利用这样一个事实：如果我们考虑m个最大元素或m个最小元素作为子序列，则最大权重差（即元素和与其余元素和的差）最大。
因此，我们将检查m个最大元素的子序列和其余数组，或m个最小元素的子序列和其余数组的最大和差。
并返回两者中的最大值。
算法
**初始化** −
maxSum , maxSumDiff, minSumDiff
**步骤1** −
sort the array in descending order.
**步骤2** −
Loop for i −> 0 to n
**步骤2.1** −
if (i < m) −> maxSumDiff += arr[i]
**步骤2.2** −
else −> maxSumDiff −= arr[i]
**步骤2** −
Loop for i −> n to 0
**步骤2.1** −
if (i > m) −> minSumDiff += arr[i]
**步骤2.2** −
else −> minSumDiff −= arr[i]
**步骤3** −
if maxSumDiff > minSumDiff −> maxSum = maxSumDiff.
**步骤4** −
if maxSumDiff < minSumDiff −> maxSum = minSumDiff.
**步骤5** −
return maxSum.
示例
程序演示了我们解决方案的工作原理：
#include <bits/stdc++.h>
using namespace std;
int maxWeightDifference(int arr[], int N, int M){
int maxabsDiff = −1000;
sort(arr, arr + N);
int sumMin = 0, sumMax = 0, arrSum = 0;
for(int i = 0; i < N; i++){
arrSum += arr[i];
if(i < M)
sumMin += arr[i];
if(i >= (N−M))
sumMax += arr[i];
}
maxabsDiff = max(abs(sumMax − (arrSum − sumMax)), abs(sumMin −
(arrSum − sumMin)));
return maxabsDiff;
}
int main(){
int arr[] = {3, 1, 6, 9, 4} ;
int M = 3;
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum weight difference is "<<maxWeightDifference(arr,N, M);
return 0;
}输出
The maximum weight difference is 15
更新于：2020年12月9日
196 次浏览
广告