Hiệu tối đa giữa 2 tập con m phần tử trong mảng C

Cho mảng và số m. Tìm hiệu lớn nhất giữa tổng m phần tử lớn nhất và tổng m phần tử nhỏ nhất.

Ví dụ

Đầu vào

arr = {1, 2, 3, 4, 5}, m = 3

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

Giải thích - 3 lớn nhất: 3,4,5 (tổng=12). 3 nhỏ nhất: 1,2,3 (tổng=6). Hiệu = 12-6 = 6.

Đầu vào

arr = {10, 13, 22, 8, 16, 14}, m = 4

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

Giải thích - 4 lớn nhất: 22,16,14,13 (tổng=65). 4 nhỏ nhất: 8,10,13,14 (tổng=45). Hiệu = 65-45 = 20.

Phương pháp

• Sắp xếp mảng tăng dần
• Tính tổng m phần tử đầu (minsum)
• Tính tổng m phần tử cuối (maxsum)
• Trả về maxsum - minsum

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 find_diff(int arr[], int length, int m) {
    sort(arr, length);
    int maxsum = 0, minsum = 0;
    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;
    printf("Hiệu tối đa 2 tập con %d phần tử: %d", m, find_diff(arr, 7, m));
    return 0;
}

Kết quả

Hiệu tối đa 2 tập con 3 phần tử: 12