โปรแกรมหาความต่างน้ำหนักสูงสุดใน C++

ให้อาร์เรย์ arr[] และตัวเลข M หา M องค์ประกอบ ที่ผลต่างสัมบูรณ์ระหว่างผลรวม M ตัวนั้น กับผลรวมตัวที่เหลือ มากที่สุด

ตัวอย่าง: arr=[3,1,6,9,4], M=3 → 15 เลือก 4,6,9 ผลรวม 19, เหลือ 3+1=4, |19-4|=15

วิธีแก้ปัญหา

ความต่างมากที่สุดเกิดจากการเลือก M ตัวที่ใหญ่ที่สุด หรือ M ตัวที่เล็กที่สุด คำนวณทั้ง 2 กรณี เลือกค่ามากกว่า

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int maxWeightDifference(int arr[], int N, int M) {
    sort(arr, arr+N);
    int sumMin = 0, sumMax = 0, total = 0;
    for (int i = 0; i < N; i++) {
        total += arr[i];
        if (i < M) sumMin += arr[i];
        if (i >= N-M) sumMax += arr[i];
    }
    int diff1 = abs(sumMax - (total - sumMax));
    int diff2 = abs(sumMin - (total - sumMin));
    return max(diff1, diff2);
}

int main() {
    int arr[] = {3,1,6,9,4};
    int M = 3, N = 5;
    cout << maxWeightDifference(arr, N, M); // 15
    return 0;
}

อินพุต

arr[] = {3, 1, 6, 9, 4}, M = 3

เอาต์พุต

15