数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学C语言中k个元素组与数组其余部分的最大差值
给定一个大小为N的整数数组和一个数字k。该数组包含随机顺序的整数。任务是找到k个元素组与数组其余部分之间的最大差值。数组将被分成两部分。第一部分是从中取出的一组k个元素，第二部分是数组的其余元素。我们必须选择k个元素，使得两组元素的和之间的差值最大。
如果k较小（<=数组大小的一半），则最小的k个元素的和最小，其余N-k个元素的和最大。因此，最大差值为−（其余N-k个元素的和） - （最小的k个元素的和）。
如果k较大（>数组大小的一半），则最大的k个元素的和最大，其余N-k个元素的和最小。因此，最大差值为（最大的k个元素的和） - （其余N-k个元素的和）。
输入
Arr[] = { 2,5,6,1,3,2,1,4 }. k=3输出 - k个元素组与数组其余部分之间的最大差值 - 16
解释 - 这里k较小，所以最小的3个数的和最小。
最小的3个数 - 1,1,2 和为4
其余N-k = 5个数: 2,3,4,5,6 和为20
最大差值：20-4 = 16
输入
Arr[] = { 2,2,3,4,8,3,4,4,8,7 }. k=6输出 - k个元素组与数组其余部分之间的最大差值 - 25
解释 - 这里k较大，所以最大的6个数的和最大。
最大的6个数 - 8,8,7,4,4,4, 和为35
其余N-k = 4个数 - 2,2,3,3 和为10
最大差值 - 35-10=
下面程序中使用的方案如下
声明一个包含随机顺序整数的数组。( Arr[] )
创建一个变量来存储数组的大小。(N)
函数maxKDiff( int Arr[],int n, int k)用于计算数组中元素的第一个和最后一个索引之间的最大差值(maxD)。
计算整个数组的和并存储在arrsum中。
首先计算最小的k个元素的和。使用for循环 ( i=0;i<k)
如果k较小，则最小的k个元素的和最小 -
在D1中存储abs((整个数组的和) - (最小的k个元素的和的两倍))。两倍是因为数组和也包含这些元素。
k较大，则最大的k个元素的和最大 -
在D2中存储abs((整个数组的和) - (最大的k个元素的和的两倍))。两倍是因为数组和也包含这些元素。
比较D1与D2，并将最大值存储在maxD中。
返回maxD作为结果。
示例
#include <stdio.h>
#include <math.h>
// function for finding maximum group difference of array
int maxKDiff (int arr[], int n, int k){
// sum of array
int arrsum = 0;
int i;
for(i=0;i<n;i++)
arrsum+=arr[i];
//sum of smallest k
int sumk=0;
for(i=0;i<k;i++)
sumk+=arr[i];
// difference for k-smallest
int D1 = abs(arrsum - 2*sumk);
//sum of largest k elements
sumk=0;
int j=0;
for(i=n-1;j<4;i--){
sumk+=arr[i]; j++;
}
// difference for k-largest
int D2 = abs(arrsum - 2*sumk);
int maxD=D1>=D2?D1:D2;
// return maximum difference value
return maxD;
}
// driver program
int main(){
int arr[] ={ 2,3,2,10,7,12,8};
int n = 7;
int k = 3;
sort(arr,n); // to sort array in ascending order
printf("Maximum difference between the group of k-elements and rest of the array : %d" , maxKDiff(arr,n,k));
return 0;
}输出
如果我们运行上述代码，它将生成以下输出 -
Maximum difference between the group of k-elements and rest of the array : 30
505 次浏览
