Hiệu tối đa giữa nhóm k phần tử và phần còn lại của mảng trong C

Cho mảng kích thước N và số k. Chia mảng thành 2 nhóm: nhóm k phần tử và nhóm N-k phần tử còn lại. Chọn k phần tử sao cho hiệu giữa tổng 2 nhóm lớn nhất.

Ví dụ

Đầu vào

Arr[] = { 2, 5, 6, 1, 3, 2, 1, 4 }, k = 3

Đầu ra - Hiệu tối đa: 16

Giải thích - k = 3 ≤ N/2, chọn 3 số nhỏ nhất: 1,1,2 (tổng=4). Phần còn lại: 2,3,4,5,6 (tổng=20). Hiệu = 20-4 = 16.

Đầu vào

Arr[] = { 2, 2, 3, 4, 8, 3, 4, 4, 8, 7 }, k = 6

Đầu ra - Hiệu tối đa: 25

Giải thích - k = 6 > N/2, chọn 6 số lớn nhất: 8,8,7,4,4,4 (tổng=35). Phần còn lại: 2,2,3,3 (tổng=10). Hiệu = 35-10 = 25.

Phương pháp

• Sắp xếp mảng tăng dần
• Tính tổng toàn mảng (arrsum)
• Tính tổng k phần tử nhỏ nhất (sumk) → D1 = |arrsum - 2*sumk|
• Tính tổng k phần tử lớn nhất (sumk) → D2 = |arrsum - 2*sumk|
• Trả về max(D1, D2)

Chương trình mẫu

#include <stdio.h>
#include <stdlib.h>

void sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = i+1; j < n; j++)
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
}

int maxKDiff(int arr[], int n, int k) {
    int arrsum = 0;
    for (int i = 0; i < n; i++) arrsum += arr[i];
    
    int sumk = 0;
    for (int i = 0; i < k; i++) sumk += arr[i];
    int D1 = abs(arrsum - 2 * sumk);
    
    sumk = 0;
    for (int i = n-1, j = 0; j < k; i--, j++) sumk += arr[i];
    int D2 = abs(arrsum - 2 * sumk);
    
    return (D1 > D2) ? D1 : D2;
}

int main() {
    int arr[] = {2, 3, 2, 10, 7, 12, 8};
    int n = 7, k = 3;
    sort(arr, n);
    printf("Hiệu tối đa: %d", maxKDiff(arr, n, k));
    return 0;
}

Kết quả

Hiệu tối đa: 30