เราได้รับอาร์เรย์ของจำนวนเต็มบวกและลบ ภารกิจคือการค้นหาความแตกต่างสูงสุดระหว่างชุดย่อยที่เป็นบวกและลบขององค์ประกอบที่มีอยู่ในอาร์เรย์ เนื่องจากเรามีเซตย่อยของจำนวนบวกและลบ จากนั้นผลต่าง (ผลบวก) - (ผลรวมเชิงลบ) จะสูงสุดเสมอ เนื่องจากการลบค่าเนกาทีฟจะเพิ่มเข้าไป การแปลงค่าลบทั้งหมดเป็นค่าบวกและการเพิ่มองค์ประกอบทั้งหมดของอาร์เรย์จะทำให้ได้ผลลัพธ์ที่ต้องการ เรามาดูตัวอย่างเพื่อความเข้าใจกัน −
ป้อนข้อมูล − Arr[] ={ -2, 0, -3, 8, 10, 12, -4 }
ผลผลิต − ความแตกต่างสูงสุดระหว่างสองเซตย่อย − 39
คำอธิบาย − เซตย่อยของจำนวนเต็มบวก {0, 8,10,12} ผลรวมคือ 30
เซตย่อยของจำนวนเต็มลบ { -2, -3, -4 } ผลรวมคือ -9
ความแตกต่างสูงสุดจะอยู่ที่ 30 - (-9) =39
ป้อนข้อมูล − Arr[] ={ -5, -15, -3, -2, 10, 20, 15 }
ผลผลิต − ความแตกต่างสูงสุดระหว่างสองส่วนย่อย − 70
คำอธิบาย − เซตย่อยของจำนวนเต็มบวก { 10, 20, 15 } ผลรวมคือ 45
เซตย่อยของจำนวนเต็มลบ { -5, -15, -3, -2 } ผลรวมคือ -25
ความแตกต่างสูงสุดจะอยู่ที่ 45 - (-25) =70
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
เราใช้อาร์เรย์จำนวนเต็มที่มีจำนวนเต็มบวกและลบเป็น Arr[]
-
ฟังก์ชัน subsetDifference( int arr[],int n) คือการค้นหาความแตกต่างสูงสุดระหว่างชุดย่อยของจำนวนเต็มลบและจำนวนเต็มบวกสองชุด ต้องใช้อาร์กิวเมนต์สองตัว ตัวหนึ่งคือตัวอาร์เรย์เอง และอีกตัวคือขนาด n
-
ใช้ตัวแปร sum=0 เพื่อเก็บผลรวมขององค์ประกอบทั้งหมดของอาร์เรย์
-
เริ่มจากด้านซ้าย สำรวจแต่ละองค์ประกอบของอาร์เรย์โดยใช้ for loop ( i=0;i
-
หากองค์ประกอบปัจจุบันเป็นค่าลบ (<0) ให้คูณด้วย -1.( arr[i]=arr[i]*-1 )
-
เพิ่มแต่ละองค์ประกอบลงในผลรวม
-
คืนค่าผลรวมเป็นความแตกต่างของชุดย่อยสูงสุดที่เป็นไปได้
ตัวอย่าง
#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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Maximized difference between two subsets: 70
