크기 N과 숫자 k의 정수 배열이 제공됩니다. 배열은 임의의 순서로 정수로 구성됩니다. 작업은 k-요소 그룹과 나머지 어레이 사이의 최대 차이를 찾는 것입니다. 배열은 두 부분으로 나뉩니다. 첫 번째 부분은 제거된 k-요소 그룹이고 두 번째 부분은 배열의 나머지 요소입니다. 두 그룹의 요소 합 간의 차이가 최대가 되도록 k 요소를 선택해야 합니다.
k가 더 작으면(<=배열 크기의 절반) 가장 작은 k 요소의 합이 가장 작고 나머지 N-k 요소의 합이 가장 큽니다. 따라서 최대 차이는 - (나머지 N-k 요소의 합) - (가장 작은 k-요소의 합)입니다.
k가 더 크면(> 배열 크기의 절반) 가장 큰 k 요소의 합이 가장 크고 나머지 N-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 요소는 최소 합을 갖습니다 -
-
D1에 abs((전체 배열의 합) - (2*최소 k 요소의 합))을 저장합니다. 배열 sum에도 이러한 요소가 있기 때문에 두 번.
k는 가장 큰 k 요소가 가장 높은 합을 갖는 것보다 큽니다 -
-
D2에 abs((전체 배열의 합) - (2*가장 높은 k 요소의 합))을 저장합니다. 배열 sum에도 이러한 요소가 있기 때문에 두 번.
-
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