Tối đa hóa sự khác biệt giữa hai tập hợp con của một tập hợp có phủ định trong C

Chúng ta được cung cấp với một mảng các số nguyên dương và âm. Nhiệm vụ là tìm sự khác biệt lớn nhất giữa các tập con dương và âm của các phần tử có trong mảng. Như chúng ta có các tập con của số dương và số âm. Khi đó, sự khác biệt (tổng số dương) - (tổng số phủ định) sẽ luôn là cực đại. Điều này là do trừ các phủ định sẽ thêm chúng. Chuyển đổi tất cả các phủ định thành dương và thêm tất cả các phần tử của mảng sẽ tạo ra kết quả mong muốn. Hãy để chúng tôi xem các ví dụ để hiểu -

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

Đầu ra - Sự khác biệt tối đa giữa hai tập hợp con - 39

Giải thích - tập hợp con số nguyên dương {0, 8,10,12} tổng là 30

Tập hợp con số nguyên âm {-2, -3, -4} tổng là -9

Chênh lệch tối đa sẽ là 30 - (-9) =39

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

Đầu ra - Sự khác biệt tối đa giữa hai tập hợp con - 70

Giải thích - tập hợp con số nguyên dương {10, 20, 15} tổng là 45

Tổng số nguyên âm {-5, -15, -3, -2} là -25

Chênh lệch tối đa sẽ là 45 - (-25) =70

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Chúng tôi lấy một mảng số nguyên có các số nguyên dương và âm là Arr []

• Hàm subsetDifference (int arr [], int n) là để tìm sự khác biệt lớn nhất giữa hai tập con của số nguyên âm và dương. Nó cần hai đối số, một là chính mảng và đối số kia là kích thước n.

• Lấy một biến sum =0 để lưu trữ tổng của tất cả các phần tử của mảng.

• Bắt đầu từ bên trái, lướt qua từng phần tử của mảng bằng vòng lặp for (i =0; i

• Nếu phần tử hiện tại là âm (<0), hãy làm cho phần tử dương bằng cách nhân với -1. (Arr [i] =arr [i] * - 1)

• Thêm từng phần tử vào tổng.

• Trả lại tổng dưới dạng chênh lệch tập hợp con lớn nhất có thể.

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;
}
// Driver Code
int main(){
   int arr[] = { -1, 3, 5, 17, -32, 12 };
   int n = 6;
   printf("Maximized difference between subsets : %d", subsetDifference(arr, n));
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Maximized difference between two subsets: 70