งานคือการหาความต่างมากที่สุดระหว่างผลรวมของ m องค์ประกอบในอาร์เรย์ สมมติเรามีอาร์เรย์และตัวเลข m เราจะหาผลรวมของ m ตัวเลขที่มากที่สุดก่อน แล้วลบผลรวมของ m ตัวเลขที่น้อยที่สุดออก เพื่อให้ได้ความต่างสูงสุด ดังนั้นสิ่งสำคัญคือการหาสองเซตย่อยของ m ตัวเลขที่มีผลรวมมากที่สุดและน้อยที่สุด
ตัวอย่าง
อินพุต
arr = {1, 2, 3, 4, 5} ; m = 3
เอาต์พุต
ความต่างสูงสุดที่นี่คือ: 6
คำอธิบาย — ตัวเลข 3 ตัวที่มากที่สุดคือ 3, 4, 5 ผลรวมคือ 12 ตัวเลข 3 ตัวที่น้อยที่สุดคือ 1, 2, 3 ผลรวมคือ 6 ดังนั้นความต่างสูงสุดคือ 12-6 = 6
อินพุต
arr = {10, 13, 22, 8, 16, 14} ; m = 4
เอาต์พุต
ความต่างสูงสุดที่นี่คือ: 20
วิธีการที่ใช้ในโปรแกรม
- รับอินพุตอาร์เรย์ arr[] และตัวเลข m สำหรับสร้างเซต
- ในฟังก์ชัน find_diff() ส่งอินพุตอาร์เรย์และความยาว และคืนค่าความต่างสูงสุดของผลรวมเซต m องค์ประกอบ
- ก่อนอื่น เรียงลำดับองค์ประกอบของอาร์เรย์ arr[]
- จากนั้นหาผลรวมของ m ตัวแรกและ m ตัวสุดท้าย เพราะจะเป็น m ตัวน้อยที่สุดและ m ตัวมากที่สุดของ arr[]
- สุดท้ายคืนค่าความต่าง
- หมายเหตุ — sort(arr[], int) สมมติว่าคืนค่าอาร์เรย์ที่เรียงแล้ว
ตัวอย่างโค้ด
#include <stdio.h>
// ฟังก์ชันคำนวณความต่างสูงสุดระหว่างผลรวม m ตัวมากที่สุดและน้อยที่สุด
int find_diff(int arr[], int length, int m) {
// เรียงลำดับอาร์เรย์
sort(arr, length);
int maxsum = 0, minsum = 0;
// คำนวณความต่างสูงสุดระหว่างสองเซตย่อย m องค์ประกอบ
for(int i = 0; i < m; i++) {
minsum += arr[i];
maxsum += arr[length - i - 1];
}
return (maxsum - minsum);
}
// โปรแกรมหลัก
int main() {
int arr[] = {1, 1, 2, 3, 5, 7, 1};
int m = 3;
cout << find_diff(arr, 7, m);
return 0;
}
ผลลัพธ์
หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้ —
12
