Tối đa hiệu hai tập con của tập có số âm trong C

Cho mảng số nguyên dương và âm. Nhiệm vụ tìm hiệu lớn nhất giữa tập con số dương và tập con số âm. Vì có tập con dương và âm, hiệu (tổng dương) - (tổng âm) luôn lớn nhất. Vì trừ số âm là cộng. Chuyển tất cả số âm thành dương và cộng tất cả phần tử sẽ cho kết quả. Xem ví dụ:

Đầu vào - Arr[] = {-2, 0, -3, 8, 10, 12, -4}

Đầu ra - Hiệu tối đa giữa hai tập con = 39

Giải thích - Tập số dương {0, 8, 10, 12} tổng = 30

Tập số âm {-2, -3, -4} tổng = -9

Hiệu tối đa = 30 - (-9) = 39

Đầu vào - Arr[] = {-5, -15, -3, -2, 10, 20, 15}

Đầu ra - Hiệu tối đa = 70

Giải thích - Tập dương {10, 20, 15} tổng = 45

Tập âm {-5, -15, -3, -2} tổng = -25

Hiệu tối đa = 45 - (-25) = 70

Phương pháp chương trình

• Mảng nguyên Arr[] chứa số dương/âm.

• Hàm subsetDifference(int arr[], int n) tìm hiệu tối đa. Tham số: mảng và kích thước n.

• Biến sum=0 lưu tổng tất cả phần tử.

• Duyệt từ trái: for(i=0; i

• Nếu phần tử âm (<0) đổi thành dương bằng nhân -1.

• Cộng từng phần tử vào sum.

• Trả về sum là hiệu tập con lớn nhất.

Ví dụ

#include <stdio.h>
int subsetDifference(int arr[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < 0)
            arr[i] = arr[i] * -1;
        sum += arr[i];
    }
    return sum;
}
int main() {
    int arr[] = {-1, 3, 5, 17, -32, 12};
    int n = 6;
    printf("Hieu toi da giua cac tap con: %d", subsetDifference(arr, n));
    return 0;
}

Kết quả

Chạy code cho đầu ra:

Hieu toi da giua hai tap con: 70