資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
