Cのm要素の2つのサブセット間の最大差

タスクは、配列内のm個の要素の合計間の最大の差を見つけることです。配列と数値mがあるとすると、最初に最大のm個の数値の合計を見つけ、次に最小のm個の数値の合計を減算して最大の差を求めます。したがって、主なことは、合計が最大で合計が最小のm個の数値の2つのサブセットを見つけることです。

例を使用して、私たちがしなければならないことを理解しましょう-

入力

arr = {1,2,3,4,5} ; m=3

出力

Maximum difference here is : 6

説明 −ここで、最大の3つの数値は3,4,5で、合計は12です。最小の3つの数値は1,2,3で、合計は6です。したがって、最大または最大の差は12-6、つまり6です。

入力

arr = {10,13,22,8,16,14}; m=4

出力

Maximum difference here is : 20

説明 −ここで、最高の4つの数字は22,16,14,13で、合計は65です。最低の4つの数字は8,10,13,14で、合計は45です。したがって、最大または最大の差は65-45、つまり20です。

以下のプログラムで使用されるアプローチは次のとおりです

• セットを作成するために入力配列arr[]と数mを取ります

• find_diff（）関数では、入力配列とその長さを渡し、m個の要素のセットの合計の最大差を返します。

• ここでは、最初に配列arr[]の要素を並べ替えます。

• 次に、最初のm個と最後のm個の要素の合計を求めます。これらは最小m個と最大m個のarr[]であるためです。

• 最後に、差額を返します。

• 注-sort（arr []、int）は、ソートされた配列を返すと想定されています。

例

#include<stdio.h>
//create function to calculate maximum difference between sum of highest and lowest m elements of array
int find_diff(int arr[],int length,int m){
   //for sorting the array
   sort(arr,length);
   int maxsum=0, minsum=0;
   //calculate now max difference between two subsets of m elements
   for(int i=0;i<m;i++){
      minsum+=arr[i];
      maxsum+=arr[length-i-1];
   }
   return(maxsum-minsum);
}
// Driver program
int main(){
   int arr[]={1,1,2,3,5,7,1};
   int m=3;
   cout << find_diff(arr,7,m);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

12