작업은 배열에 있는 m개 요소의 합 사이의 가장 큰 차이를 찾는 것입니다. 배열과 숫자 m이 있다고 가정하면 먼저 가장 높은 m개의 숫자의 합을 찾은 다음 가장 낮은 m개의 숫자의 합을 빼서 최대 차이를 구합니다. 따라서 가장 중요한 것은 합이 가장 높고 합이 가장 낮은 m개의 숫자에서 두 개의 하위 집합을 찾는 것입니다.
이제 예제를 사용하여 무엇을 해야 하는지 이해합시다 -
입력
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입니다. 따라서 최대 또는 최대 차이는 20인 65-45입니다.
아래 프로그램에서 사용하는 접근 방식은 다음과 같습니다.
-
세트를 만들기 위해 입력 배열 arr[]와 숫자 m을 가져옵니다.
-
find_diff() 함수에서 우리는 입력 배열과 길이를 전달하고 m 요소 집합의 합에서 최대 차이를 반환합니다.
-
여기서 우리는 먼저 배열 arr[]의 요소를 정렬할 것입니다.
-
그런 다음 처음 m개와 마지막 m개 요소의 합은 arr[]의 최소 m개와 가장 높은 m개이므로 합을 찾습니다.
-
마침내 우리는 차액을 반환합니다.
-
참고 - 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