C中的k元素组与数组其余部分之间的最大差

  • Z时代
  • 2024-01-10
  • 分类：综合

给定一个大小为N且数字为k的整数数组。该数组由随机顺序的整数组成。任务是找出k个元素组与数组其余部分之间的最大差值。该数组将分为两部分。第一部分是取出的一组k元素，第二部分是数组的其余元素。我们必须选择k个元素，以使两组元素之和之间的差异最大。

如果k较小（<=数组大小的一半），则最小的k个元素的总和最少，其余Nk个元素的总和最大。因此，最大差为-（其余Nk个元素的总和）-（最小k个元素的总和）。

如果k较大（>数组大小的一半），则最大的k个元素的总和最大，其余Nk个元素的总和最小。因此，最大差为（最大kelement的总和）-（其余Nk元素的总和）。

输入值 

Arr[] = { 2,5,6,1,3,2,1,4 }. k=3

输出-k元素组与数组其余部分之间的最大差-16

解释-这里的k较小，因此至少3个数字的总和最小。

最少3个数字-1,1,2和= 4

剩余Nk = 5个数字：2,3,4,5,6 sum = 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

其余Nk = 4个数字-2,2,3,3 sum = 10

最大差异-35-10 =

以下程序中使用的方法如下

  • 声明一个以随机顺序包含的整数数组。（Arr []）

  • 创建一个变量来存储数组的大小。(N)

  • 函数maxKDiff（int Arr []，int n，int k）用于计算数组中元素的第一个索引与最后一个索引之间的最大差(maxD)。

  • 计算整个数组的总和并存储在arrsum中。

  • 首先是计算至少k个元素的总和。使用for循环（i = 0; i <k）

    如果k较小，则最小的k个元素的总和最小-

  • 在D1中存储abs（（整个数组的总和）-（2 *至少k个元素的总和））。两次是因为数组和也具有这些元素。

    k较大，则最大的k个元素的总和最高-

  • 在D2中存储abs（（整个数组的总和）-（2 *最高k个元素的总和））。两次是因为数组和也具有这些元素。

  • 比较D1与D2并将最大值存储在maxD中。

  • 返回maxD作为结果。

示例

#include <stdio.h>
#include <math.h>
//查找数组最大组差的函数
int maxKDiff (int arr[], int n, int k){
   //数组总和
   int arrsum = 0;
   int i;
   for(i=0;i<n;i++)
      arrsum+=arr[i];
   //最小k之和
   int sumk=0;
   for(i=0;i<k;i++)
      sumk+=arr[i];
   //K最小的差异
   int D1 = abs(arrsum - 2*sumk);
   //最大k个元素的总和
   sumk=0;
   int j=0;
   for(i=n-1;j<4;i--){
      sumk+=arr[i]; j++;
   }
   //k最大的差异
   int D2 = abs(arrsum - 2*sumk);
   int maxD=D1>=D2?D1:D2;
   //返回最大差值
   return maxD;
}
//驱动程序
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

以上是 C中的k元素组与数组其余部分之间的最大差 的全部内容， 来源链接： utcz.com/z/341150.html

回到顶部