Chúng ta được cung cấp với một mảng các số nguyên có kích thước N và một số k. Mảng bao gồm các số nguyên theo thứ tự ngẫu nhiên. Nhiệm vụ là tìm sự khác biệt lớn nhất giữa nhóm k-phần tử và phần còn lại của mảng. Mảng sẽ được chia thành hai phần. Phần đầu tiên là một nhóm k-phần tử được lấy ra và phần thứ hai là phần còn lại của các phần tử của mảng. Chúng ta phải chọn k phần tử sao cho sự khác biệt giữa tổng các phần tử trong cả hai nhóm là lớn nhất.
Nếu k nhỏ hơn (<=một nửa kích thước mảng) thì k phần tử nhỏ nhất sẽ có tổng ít nhất và N-k phần tử còn lại sẽ có tổng lớn nhất. Vậy hiệu số lớn nhất là - (tổng N-k phần tử còn lại) - (tổng k phần tử nhỏ nhất).
Nếu k lớn hơn (> một nửa kích thước mảng) thì k phần tử lớn nhất sẽ có tổng lớn nhất và N-k phần tử còn lại sẽ có tổng nhỏ nhất. Vì vậy, sự khác biệt lớn nhất là (tổng của các phần tử lớn nhất) - (tổng của N-k phần tử còn lại).
Đầu vào
Arr[] = { 2,5,6,1,3,2,1,4 }. k=3 Đầu ra - Chênh lệch tối đa giữa nhóm k-phần tử và phần còn lại của mảng - 16
Giải thích - Ở đây k nhỏ hơn nên 3 số ít nhất sẽ có tổng nhỏ nhất.
Ít nhất 3 số - 1,1,2 tổng =4
Phần còn lại N-k =5 số:2,3,4,5,6 sum =20
Chênh lệch tối đa:20-4 =16
Đầu vào
Arr[] = { 2,2,3,4,8,3,4,4,8,7 }. k=6 Đầu ra - Chênh lệch tối đa giữa nhóm k-phần tử và phần còn lại của mảng - 25
Giải thích - Ở đây k lớn hơn nên 6 số cao nhất sẽ có tổng lớn nhất.
6 số cao nhất - 8,8,7,4,4,4, tổng =35
Phần còn lại N-k =4 số - 2,2,3,3 tổng =10
Chênh lệch tối đa - 35-10 =
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Khai báo một mảng các số nguyên chứa theo thứ tự ngẫu nhiên. (Arr [])
-
Tạo một biến để lưu trữ kích thước của mảng. (N)
-
Hàm maxKDiff (int Arr [], int n, int k) được sử dụng để tính toán sự khác biệt lớn nhất (maxD) giữa chỉ mục đầu tiên và chỉ mục cuối cùng của một phần tử trong một mảng.
-
Tính tổng của toàn bộ mảng và lưu trữ trong arrsum.
-
Điều đầu tiên là tính tổng của k phần tử nhỏ nhất. Sử dụng vòng lặp for (i =0; i
Nếu k nhỏ hơn thì k phần tử nhỏ nhất sẽ có tổng ít nhất -
-
Trong D1 lưu trữ abs ((tổng của cả mảng) - (2 * tổng của ít nhất k phần tử)). Hai lần vì tổng mảng cũng có các phần tử này.
k lớn hơn thì k phần tử lớn nhất sẽ có tổng cao nhất -
-
Trong D2 lưu trữ abs ((tổng của cả mảng) - (2 * tổng của k phần tử cao nhất)). Hai lần vì tổng mảng cũng có các phần tử này.
-
So sánh D1 với D2 và lưu trữ giá trị lớn nhất trong maxD.
-
Kết quả là trả về maxD.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Maximum difference between the group of k-elements and rest of the array : 30