k要素のグループとCの配列の残りの部分との最大差

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 sum =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、sum =35

残りのN-k=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要素の合計は最小になります-

• D1にabs（（配列全体の合計）-（2 *最小k要素の合計））を格納します。配列の合計にもこれらの要素があるため、2回です。

  kは、最大のk要素の合計が最大になるよりも大きくなります-

• D2にabs（（配列全体の合計）-（2 *最高のk要素の合計））を格納します。配列の合計にもこれらの要素があるため、2回です。

• 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