Nhiệm vụ là tìm ra sự khác biệt lớn nhất giữa tổng của m phần tử trong một mảng. Giả sử chúng ta có một mảng và một số m, sau đó trước tiên chúng ta sẽ tìm tổng của m số cao nhất và sau đó trừ tổng của m số thấp nhất từ nó để có hiệu số lớn nhất. Vì vậy, điều chính là tìm hai tập con gồm m số có tổng cao nhất và tổng thấp nhất.
Bây giờ chúng ta hãy hiểu những gì chúng ta phải làm bằng cách sử dụng một ví dụ -
Đầu vào
arr = {1,2,3,4,5} ; m=3 Đầu ra
Maximum difference here is : 6
Giải thích - Ở đây 3 số cao nhất là 3,4,5 và tổng là 12. 3 số thấp nhất là 1,2,3 và tổng là 6. Vậy hiệu cao nhất hoặc lớn nhất là 12-6 là 6.
Đầu vào
arr = {10,13,22,8,16,14}; m=4 Đầu ra
Maximum difference here is : 20
Giải thích - Ở đây 4 số cao nhất là 22,16,14,13 và tổng là 65. 4 số thấp nhất là 8,10,13,14 và tổng là 45. Vì vậy, chênh lệch cao nhất hoặc tối đa là 65-45, là 20.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Lấy mảng đầu vào arr [] và một số m để tạo tập hợp
-
Trong hàm find_diff (), chúng ta đang chuyển mảng đầu vào và độ dài của nó và trả về hiệu số lớn nhất của tổng bộ gồm m phần tử.
-
Ở đây, trước tiên chúng ta sẽ sắp xếp các phần tử của mảng arr [].
-
Sau đó, chúng ta sẽ tìm tổng của m phần tử đầu tiên và m phần tử cuối cùng vì đây sẽ là m nhỏ nhất và m số cao nhất của arr [].
-
Cuối cùng, chúng tôi trả lại số tiền chênh lệch.
-
Lưu ý - sort (arr [], int) được giả sử để trả về mảng đã sắp xếp.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, chúng ta sẽ nhận được kết quả sau -
12